위클리 챌린지 > 9주차

https://programmers.co.kr/learn/courses/30/lessons/86971

 

class Solution {
    static int[] unf;
    public int find(int a){
        if(unf[a]==a) return a;
        else return unf[a]=find(unf[a]);
    }
    public void union(int a, int b){
        int fa = find(a);
        int fb = find(b);
        if(fa!=fb) unf[fa]=fb;
    }

    public void resetUnf(int n){
        for(int i=1; i<n+1; i++){
            unf[i]=i;
        }
    }

    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        unf = new int[n+1];
        resetUnf(n);
       for(int i=0; i<wires.length; i++){
           for(int j=0; j<wires.length; j++){
               if(i!=j)
               union(wires[j][0], wires[j][1]);
           }

           int idx =1;
           for(int k=1;k<n+1; k++){
                         if(k == unf[k]) {
                             idx = k;
                             break;
                         }   
           }
           int v1=0;
           for(int k=1; k<n+1; k++){
               if(find(k)==idx) v1++;
           }
           int v2 = n-v1;
           answer = Math.min(answer, Math.abs(v2-v1));
           resetUnf(n);
       }

        return answer;
    }
}

 

간선 문제라 Union&Find가 떠올라서 이렇게 풀어보았는데

그냥 간선 연결정보를 배열에 담고 이어진 노드 개수를 DFS로 구하는게 훨씬 나았을 것 같다..