[백준] 6497 : 전력난 (JAVA)

문제

BOJ 6497 : 전력난 - https://www.acmicpc.net/problem/6497

풀이

전체 가로등 중에서 최소한의 가로등만 켜서 전력을 아껴야하기 때문에, 최소 스패닝트리(MST)를 구해서, 전체 길의 길이 - MST를 구성하는 길의 길이를 해주면 된다.

MST를 구하기 위해 Kruskal Algorithm을 적용했다.

1. edge의 가중치를 기준으로 오름차순 정렬한다.
2. 가장 작은 가중치의 edge부터 확인하는데, 양 끝점이 이미 연결되어있는지 확인 후(find), 아니라면 이어준다(union).
3. 선택된 edge의 개수가 node수-1이면 종료

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true) {

            String[] inputs = br.readLine().split(" ");

            int m = Integer.parseInt(inputs[0]); // 집의 수
            int n = Integer.parseInt(inputs[1]); // 길의 수

            if(m==0 && n==0) {
                return;
            }

            int[][] edges = new int[n][3];

            int total_cost = 0;
            for (int i = 0; i < n; i++) {
                inputs = br.readLine().split(" ");

                int x = Integer.parseInt(inputs[0]);
                int y = Integer.parseInt(inputs[1]);
                int z = Integer.parseInt(inputs[2]);

                edges[i][0] = x;
                edges[i][1] = y;
                edges[i][2] = z;

                total_cost += edges[i][2];

            }

            Arrays.sort(edges, (a, b) -> a[2] - b[2]); // 간선을 기준으로 오름차순으로 정렬

            parent = new int[m + 1];
            for (int i = 1; i <= m; i++) {
                parent[i] = i;
            }

            int min_cost = 0;
            int selected_cnt = 0;
            int i = 0;
            while (true) {
                if (find(edges[i][0]) != find(edges[i][1])) { // cycle이 아니면
                    union(edges[i][0], edges[i][1]);
                    min_cost += edges[i][2];
                    selected_cnt++;
                }
                if (selected_cnt == m - 1) {
                    break;
                }
                i++;
            }
            System.out.println(total_cost - min_cost);
        }

    }

    public static int find(int idx) {
        if(parent[idx]==idx){
            return idx;
        }
        parent[idx] = find(parent[idx]);
        return parent[idx];
    }

    public static void union(int a, int b) {
        int parent_of_a = find(a);
        parent[parent_of_a] = b; // 주의,,, a의 parent를 b로 바꿔야 a가 b랑 합쳐지는 것!
    }
}

정리

✔ 알고리즘 분류 - 그래프 이론, 최소 스패닝 트리
✔ 난이도 - 🟡 Gold 4

🤦‍♀️ 오늘의 메모

• 이번 문제에서는 input에서 0 0 이 입력되면 종료한다 라는 조건이 있길래 뭔가 했더니, 0 0이 나올 때까지 반복해야하는 문제였다. 여러 문제를 풀어봤는데 이런 경우는 흔하지 않아서 뭐가 틀렸는지 모르고 헤맸다.

• union-find를 어떻게 구현하는지 잘 알아두어야겠다. 대강 알고있는대로 코드를 짜고 나니 결과값이 이상하게 나왔는데, parent[parent_of_a] = b 이렇게 a의 parent를 찾은 뒤 a의 parent 정보를 b로 바꿔주어야 a와 b가 union된다(a의 parent를 parent로 가리키던 노드도 동시에 바뀌어야하기 때문에!). a의 parent를 잘 찾아놓고 parent[b] = parent_of_a라고 써서 문제가 됐었다.

• 프림 vs 크루스칼
  프림 알고리즘 시간 복잡도 : O(V^2+E) → O(E logV)
  크루스칼 알고리즘의 시간 복잡도 : O(E logE)
  
  따라서, 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph)의 경우에 크루스칼 알고리즘이 적합하고, 그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph)의 경우는 프림 알고리즘이 적합하다.
  
  

참고 사이트

딱히 없음