백준 1197 최소 스패닝 트리 Java [최소스패닝트리, 프림]

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

최소 스패닝 트리(MST)는 최소 신장 트리라고도 하며, 풀이 방법은 2가지 있다

1. 크루스칼 알고리즘

2. 프림 알고리즘

 

크루스칼 알고리즘은 트리의 간선 중에서 가장 짧은 간선을 고르고

사이클이 생기는지 확인 후 가중치에 더하는 과정을 반복한다

 

프림 알고리즘은 한 정점에서 시작해서 방문하지 않은 정점으로 갈 수 있는 간선 중에 가장 짧은 간선을 선택하고

앞에서 고른 정점과 나중에 고른 정점들 중에 방문하지 않은 정점으로 갈 수 있는 간선을 계속 고르며

정점의 갯수 - 1번 반복한다

우선순위큐를 사용해서 짧은 간선을 우선순위로 뽑고 방문체크를 하고

정점을 기준으로 방문하지 않은 정점으로 가는 간선을 다시 큐에 넣는 과정을 정점의 갯수 - 1번 반복한다

 

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 = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        boolean[] vtd = new boolean[V+1];
        int count = V;
        int result = 0;
        ArrayList<int[]>[] nodes = new ArrayList[V+1];
        for (int v = 0; v <= V; v++) {
            nodes[v] = new ArrayList<>();
        }
        for (int e = 0; e < E; e++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());
            nodes[A].add(new int[]{B,C});
            nodes[B].add(new int[]{A,C});
        }
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        queue.add(new int[]{1, 0});
        while (count > 0 && !queue.isEmpty()) {
            int[] now = queue.poll();
            if (vtd[now[0]]) continue;
            vtd[now[0]] = true;
            count--;
            result += now[1];
            for (int[] node : nodes[now[0]]) {
                if (!vtd[node[0]]) queue.add(node);
            }
        }
        System.out.println(result);
    }
}