[백준 JAVA] 회귀한 프로그래머의 최소신장트리 다시풀기

 

 

최소 신장 트리 (MST)

• 그래프에서 최소 비용 문제
  1. 두 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 ⇒ MST
  2. 두 정점 사이의 최소 비용의 경로 찾기 ⇒ 최단 경로
     1. 가중치 X : 무조건 BFS
     2. 가중치 O
        1. 양의 가중치만 허용 : 다익스트라
        2. 음의 가중치도 허용 : 벨만포드, 플루이드 워셜
• 신장 트리
  • n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리
• 최소 신장 트리 (Minimum Spanning Tree)
  • 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

 

 KRUSKAL 알고리즘

• 간선을 하나식 선택해서 MST를 찾는 알고리즘
  1. 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬
  2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴
     • 사이클이 존재하면 남아 있는 간선 중 그 다음으로 가중치가 낮은 간선 선택
  3. n-1 개의 간선이 선택될 때까지 2를 반복

 

 PRIM 알고리즘

• 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식
  1. 임의 정점을 하나 선택해서 시작
  2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
  3. 모든 정점이 선택될 때 까지 2 과정을 반복
• 서로소인 2개의 집합(2 disjoint-sets) 정보를 유지
  • 트리 정점들(tree vertices) - MST를 만들기 위해 선택된 정점들
  • 비트리 정점들(non-tree vertices) - 선택 되지 않은 정점들

 

이 중에서 자주 사용하던 프림을 중심으로 우선 문제 풀이를 해보겠다.

 

최소 스패닝 트리

 

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

 

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

public class Main {
    public static int V, E;
    public static List<int[]>[] list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        list = new List[V + 1];
        for(int i = 1; i <= V; i++){
            list[i] = new ArrayList<>();
        }

        for(int i = 0; i < E; i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            list[from].add(new int[] {to, cost});
            list[to].add(new int[] {from, cost});
        }

        System.out.println(prim());

    }
    public static int prim(){
        int ans = 0;
        int[] visited = new int[V + 1];
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[1], o2[1]));
        pq.offer(new int[] {1, 0});

        while(!pq.isEmpty()){
            int[] cur = pq.poll();
            int node = cur[0];
            int cost = cur[1];

            if(visited[node] == 1) continue;

            visited[node] = 1;
            ans += cost;

            for(int[] near : list[node]){
                if(visited[near[0]] == 1) continue;
                pq.offer(near);
            }
        }

        return ans;
    }
}