네트워트 연결 - 1922번

---

풀이 방법

최소 비용 신장 트리를 만드는 문제이다.

그리디 방법을 사용해서 트리를 만들었는데 각 경로를 나타내는 Node 클래스를 만들어서 priorityQueue를 이용했다.

 

 

내 코드

package com.company;

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        ArrayList<ArrayList<Node>> list = new ArrayList<>();
        boolean[] visited = new boolean[N + 1];

        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
        }

        int start = 100000;
        int cost = 100000;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            if (cost > c) {
                start = a;
                cost = c;
            }

            list.get(a).add(new Node(a, b, c));
            list.get(b).add(new Node(b, a, c));
        }

        for (int i = 0; i <= N; i++) {
            Collections.sort(list.get(i));
        }

        int min = 0;

        PriorityQueue<Node> q = new PriorityQueue<>();

        q.add(new Node(0, start, 0));

        while (!q.isEmpty()) {
            Node n = q.poll();

            if (visited[n.b])
                continue;

            min += n.c;
            visited[n.b] = true;

            for (int i = 0; i < list.get(n.b).size(); i++) {
                if (!visited[list.get(n.b).get(i).b]) {
                    q.add(list.get(n.b).get(i));
                }
            }
        }

        System.out.println(min);
    }
}

class Node implements Comparable<Node> {
    int a;
    int b;
    int c;

    Node(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }

    @Override
    public int compareTo(Node other) {
        if (this.c < other.c)
            return -1;
        return 1;
    }
}