프로그래머스 - 9주차 위클리 챌린지- 전력망을 둘로 나누기

[문제 바로가기]

 

1. 유형

트리, union-find

 

2. 풀이

2-1. 해설

처음 접근법은 2가지 묶음으로 나눠야 합니다. 그러기 위해서 저는 Union-find를 사용했습니다.

 

시뮬레이션을 돌려봅시다.  예제1번에서 처럼 4-7간선을 지워봅시다.

그리고 union-find를 돌리면, 아래 그림처럼 배열이 초기화 될거에요.

그럼 1의 개수와 7의 개수의 차이를 구하면 끝! 이것을 간선의 수 만큼 반복해서 최소값을 구해줍니다.

3. 코드

import java.util.*;
class Solution {
    static int p[], MIN=987654321;
    public int solution(int n, int[][] wires) {
        int answer = -1;
        for(int i=0; i<n; i++){        
            init(n+1);
            for(int j=0; j<n-1; j++){
                if(j==i) continue;
                int a=wires[j][0]; int b=wires[j][1];
                union(a,b);
            }
            check(n+1);
        }
        answer = MIN;
        return answer;
    }
    static void check(int n){
        int cnt=1;
        for(int i=2; i<n; i++){
            p[i]=find(i);
            if(p[1]==p[i]){
                cnt++;
            }
        }
        int cnt2=n-1-cnt;
        int ans=Math.abs(cnt2-cnt);
        MIN = Math.min(ans, MIN);
    }
    static void init(int n){
        p = new int[n];
        for(int i=0; i<n; i++){
            p[i]=i;
        }
    }
    static void union(int a, int b){
        a= find(a);
        b= find(b);
        if(a<b){
            p[b]=a;
        }else{
            p[a]=b;
        }
    }
    static int find(int a){
        if(a==p[a]){
            return a;
        }     
        return p[a] = find(p[a]);
    }
}