[백준]JAVA - 1922번: 네트워크 연결

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

1922번: 네트워크 연결

풀이

이번 문제는 최소 비용 신장 트리 (MST) 유형의 문제이다. 해결 방법으로는 크루스칼 알고리즘과 프림 알고리즘이 있다.

필자는 사실 크루스칼 알고리즘을 처음 들어본다. 그래서 한 번 정리해봤다.

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

간단하게 설명하자면 최소 가중치를 가지고 (정점 개수 - 1)개의 간선으로 모든 정점을 이어주는 알고리즘이다. 

알고리즘의 작동 원리만 이해한다면 이 문제는 쉽게 해결할 수 있다.

 

크루스칼 알고리즘은 Union-Find를 이용한다.

Union 은 그래프에서 상호 간의 연결을 기록해주는 역할을 하고, Find 는 x, y 노드 간의 연결성이 있는지를 찾는 메서드이다. 

 

<최종코드>

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;
		
        int ComputerCnt = Integer.parseInt(br.readLine()); // 컴퓨터 개수
        int lineCnt = Integer.parseInt(br.readLine());     // 간선 개수
		
        parent = new int[ComputerCnt+1];
        PriorityQueue<Node> pq = new PriorityQueue<>();
		
        for (int i=0; i<lineCnt; 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=0; i<ComputerCnt; i++) {
            parent[i] = i;
        }
		
        int ans = 0;
        while (!pq.isEmpty()) {
            Node node = pq.poll();
			
            // 두 개의 정점이 부모 노드가 다른 경우
            if (find(node.s) != find(node.e)) {
                union(node.s, node.e);
                ans += node.v;
            }
        }
		
        System.out.println(ans);
    }
	
    public static void union(int v1, int v2) {
        int parent1 = find(v1);
        int parent2 = find(v2);
		
        if (parent1 < parent2) {
            parent[parent2] = parent1;
        } else {
            parent[parent1] = parent2;
        }
    }
	
    public static int find(int v) {
        if (parent[v] == v) {
            return v;
        } else {
            return parent[v] = find(parent[v]);
        }
    }
}