[백준 1197 JAVA] 최소 스패닝 트리

가장 기본 mst (최소 스패닝(신장) 트리) 문제

 

푸는 방법은 크루스칼 , 프림 알고리즘이 있다.

 

나는 구현이 비교적 간단한 프림 알고리즘으로 풀었다

 

프림알고리즘이란, 간선들을 가중치 순으로 정렬하고, 정렬된 가중치 순으로 간선을 확인하며, 간선의 목적지를 방문했는지, 안했는지 체크하며 진행하는 방식이다.

 

우선순위 큐에 방문한 노드와 연결된 간선을 넣은 뒤, 우선순위큐에서 하나씩 빼 체크한다면 노드끼리 안 이어져있을 경우도 없다.

 

문제에서 주의할점 : 가중치의 범위가 integer와 일치하기 때문에 overflow방지를 위해 Long타입을 써줘야한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Node implements Comparable<Node> {
    int dir, weight;

    public Node(int dir, int weight) {
        this.dir = dir;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
}

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        LinkedList<Node>[] graph = new LinkedList[V + 1];
        for (int i = 1; i <= V; i++) {
            graph[i] = new LinkedList<>();
        }
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());
            graph[A].add(new Node(B, C));
            graph[B].add(new Node(A, C));
        }
        boolean[] visit = new boolean[V + 1];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(1, 0));
        long weight = 0;
        while (!pq.isEmpty()) {
            Node n = pq.poll();
            if (visit[n.dir]) continue;
            visit[n.dir] = true;
            weight += n.weight;
            LinkedList<Node> temp = graph[n.dir];
            for (Node node : temp) {
                if (!visit[node.dir]) pq.add(node);
            }
        }
        System.out.println(weight);
    }
}