백준 최소 스패닝 트리 - 1197

❤️문제링크

1. 문제설명

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다

• 여기서 잠깐, 최소 스패닝 트리란?

2. 문제풀이

📚 조건

정점의 개수 V (1 <= V <= 10,000)
간선의 개수 E (1<= E <= 100,000)
간선 가중치 value ( |value| <= 1,000,000)

크루스칼 알고리즘은 간선 위주로 탐색을 진행하고 프림 알고리즘은 정점 위주로 탐색을 진행한다.
간선의 개수가 적은 경우 크루스칼이 더 용이하며 많은 경우 정점 위주 탐색인 프림이 더 용이하다. 둘 다 시간복잡도는 O(ElogV)로 같다.

3. 코드

한 번도 풀어보지 않았던 프림 알고리즘의 방식으로 풀어보았다.

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

public class Main {
    static int total;
    static List<Node>[] list;
    static boolean[] visited;
    static class Node implements Comparable<Node>{
        int to;
        int value;

        public Node(int to, int value) {
            this.to = to;
            this.value = value;
        }

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

    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());

        list = new ArrayList[v+1];
        visited = new boolean[v+1];
        for(int i=1; i<v+1; i++) {
            list[i] = new ArrayList<>();
        }

        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 w = Integer.parseInt(st.nextToken());
            list[a].add(new Node(b,w));
            list[b].add(new Node(a,w));
        }

        prim(1);
        System.out.println(total);
    }

    static void prim(int start) {
        Queue<Node> pq = new PriorityQueue<>();

        pq.add(new Node(start,0));
        while(!pq.isEmpty()) {
            Node p = pq.poll();
            int node = p.to;
            int weight = p.value;

            if(visited[node]) continue;
            // 선택한 간선의 정점으로부터 가장 낮은 가중치 갖는 정점 선택
            visited[node]= true;
            total += weight;

            //해당 정점과 인접한 모든 노드 우선순위 큐에 저장
            for(Node next : list[node]) {
                if(!visited[next.to]) {
                    pq.add(next);
                }
            }
        }

    }
}