[백준] 1922번. 네트워크 연결(JAVA)

문제

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

---

풀이(15분)

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

class Main {
    static int[] parent;
    static List<Node> nodeList = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        parent = new int[n];
        for(int i = 0; i < n; i++){
            parent[i] = i;
        }

        int m = Integer.parseInt(br.readLine());
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) - 1;
            int end = Integer.parseInt(st.nextToken()) - 1;
            int cost = Integer.parseInt(st.nextToken());
            nodeList.add(new Node(start, end, cost));
        }

        Collections.sort(nodeList); // 정렬

        // 크루스칼 알고리즘
        int totalCost = 0;
        for(Node node : nodeList){
            if(find(node.start) != find(node.end)){
                totalCost += node.cost;
                union(node.start, node.end);
            }
        }

        System.out.println(totalCost);
    }

    // Union 연산 (작은 인덱스를 부모로 설정)
    static void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (rootX < rootY) {
                parent[rootY] = rootX;
            } else {
                parent[rootX] = rootY;
            }
        }
    }

    // Find 연산 (경로 압축 포함)
    static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 경로 압축
        }
        return parent[x];
    }
    static class Node implements Comparable<Node>{

        int start;
        int end;
        int cost;
        public Node(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }

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

---

문제 풀이 전략

 

보자마자 최소 신장 트리 - 크루스칼 알고리즘이 떠올랐기 때문에 그렇게 어렵지는 않은 문제였다.

 

크루스칼 알고리즘을 떠올린 이유는 다음과 같다.

1. 사이클이 존재하지 않아야 한다.(존재해도 상관은 없겠지만 최소 비용 측면에서 굳이 존재해야 하는 이유가 없다.)

2. 건너서 연결되더라도 연속되어서 연결된 것으로 볼 수 있다.

 

만약 크루스칼 알고리즘과  union-find 알고리즘을 잘 모른다면 참고하자.

[도구정리] Union-Find 알고리즘

[도구정리] 최소 신장 트리(MST) - 크루스칼(kruskal) 알고리즘