[프로그래머스] 전력망을 둘로 나누기 (유니온 파인드 Disjoint Set)

문제 소개

오늘 풀었던 전력망을 둘로 나누기 - 프로그래머스 문제를 정리합니다.
이 문제는 트리 구조에서 간선 하나를 끊어 두 개의 서브트리로 나눌 때, 송전탑 개수 차이를 최소화하는 경우를 찾는 문제입니다.

문제 링크: 전력망을 둘로 나누기 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 모든 간선에 대해 하나씩 끊어보기
2. 간선을 끊은 상태에서 유니온 파인드로 두 집합 구성
3. 각 집합 크기를 계산 후 차이를 기록
4. 최소 차이를 정답으로 선택

---

해결 과정 및 코드

핵심 아이디어

1. 전선 하나를 끊으면 두 개의 트리로 나뉨 → 이 두 트리의 송전탑 개수 차이를 구함
2. 간선 하나를 제외한 상태에서 유니온 파인드를 통해 서로소 집합 구성
3. 각 송전탑의 루트를 찾고, 루트 기준으로 카운팅하여 두 트리 크기 비교
4. 이 작업을 모든 간선에 대해 반복하며 최소 차이값을 업데이트

코드

시간 복잡도 : O(E × N)

import java.util.*;

class Solution {
    static int [] parents;
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        parents = new int[n+1];
        for (int i = 0; i < wires.length; i++) {
            cuttingWires(n, i, wires); // 간선 하나 제거
            answer = Math.min(answer, countDiff(parents)); // 두 트리 차이 계산
        }
        return answer;
    }
    
    // 간선 i번째를 제외하고 나머지로 유니온 파인드 구성
    private void cuttingWires(int n, int cuttingIdx, int[][] wirtes){
        init();
        for (int i = 0; i < wirtes.length; i++) {
            if (i == cuttingIdx) continue;
            union(wirtes[i][0], wirtes[i][1]);
        }
    }
    
    // 두 집합의 크기 차이 계산
    private int countDiff(int[] parents) {
        int n = parents.length - 1;
        int root = find(1), count = 0;
        for (int i = 1; i <= n; i++) {
            if (find(i) == root) count++;
        }
        return Math.abs((n - count) - count);
    }
    
    // 서로소 집합 초기화
    private void init(){
        for (int i = 1; i < parents.length; i++) {
            parents[i] = i;
        }
    }
    
    // 루트 찾기 (경로 압축)
    private int find(int a){
        if (parents[a] == a) return a;
        return parents[a] = find(parents[a]); // 경로 압축
    }
    
    // 집합 합치기
    private void union(int a, int b){
        int rootA = find(a), rootB = find(b);
        parents[rootB] = rootA;
    }
}