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

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

1197번: 최소 스패닝 트리

풀이

위 문제는 최소 스패닝 트리 문제로 해결 방법은 프림, 크루스칼 두 가지가 존재한다.

필자는 두 가지 방법에 대해서 잘 모르는 상태였고, 해당 알고리즘 해결법을 먼저 숙지한 다음에 다시 문제에 접근했다.

 

우선, 크루스칼을 이용해서 문제를 해결했으며 해당 내용을 모른다면 아래를 참고하는 걸 추천한다.

자바 최소 비용 신장 트리(MST), 크루스칼 알고리즘(Kruskal Algorithm) 정의

크루스칼에 대해서 간단하게 설명하자면 입력된 모든 간선을 오름차순으로 정렬한 후에 가장 작은 값부터 골라서 union-find 과정을 거쳐서 (정점-1) 개의 간선을 선택하는 것이다.

 

1. 우선 순위 큐에 모든 간선을 넣는다.

2. 가중치가 최소인 간선부터 하나씩 꺼내서 union-find 과정을 거친다.

3. 간선이 정점-1개가 될 때까지 2번 과정을 반복한다.

 

<최종코드>

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

public class Main {
    static int[] parent;
    
    public static class Node implements Comparable<Node> {
        int s;
        int e;
        int v;
        
        public Node (int s, int e, int v) {
            this.s = s;
            this.e = e;
            this.v = v;
        }
        
        public int compareTo (Node o) {
            return this.v - o.v;
        }
    }
    
    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()); // 간선의 개수
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        parent = new int[V+1];
        
        for (int i=0; i<E; i++) {
            st = new StringTokenizer(br.readLine());
            
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            
            pq.add(new Node(start, end, value));
        }
        
        for (int i=1; i<=V; i++) {
            parent[i] = i;
        }
        
        int ans = 0;
        while (!pq.isEmpty()) {
            Node now = pq.poll();
            
            if (find(now.s) != find(now.e)) {
                union(now.s, now.e);
                ans += now.v;
            }
        }
        
        System.out.println(ans);
    }
    
    public static void union (int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        
        if (p1 < p2) parent[p2] = p1;
        else parent[p1] = p2;
    }
    
    public static int find (int o) {
        if (parent[o] == o) return o;
        else return parent[o] = find(parent[o]);
    }
}