프로그래머스 전력망을 둘로 나누기 (JAVA)

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

코딩테스트 연습 - 전력망을 둘로 나누기

 

저는 해당 문제를 union find set을 이용하여 문제를 해결하였습니다.

간선을 하나씩 빼고 각각의 간선에 대해 점을 union 시키고, 마지막으로 각각의 영역을 개수를 세고 이를 빼 주었습니다.

영역의 개수를 샐때는 1번 점의 값과 같은 값은 1번영역, 다른 값을 가지면 2번 영역으로 하여 이 둘의 차를 구하였습니다.

 

import java.util.*;
class Solution {
    public int solution(int n, int[][] wires) {
        int answer = 100;
        int[] parent = new int[n+1];
        for(int i = 0 ; i < wires.length ; i++){
            init(parent,n);
            for(int j = 0 ; j < wires.length ; j++){
                if(i == j){
                    continue;
                }
                Union(parent,wires[j][0] , wires[j][1]);
            }
            answer = Math.min(answer,calDiff(parent,n));
        }
        return answer;
    }
    private int calDiff(int[] parent, int n){
        int top = findSet(parent,1);
        int[] result = new int[] {0,0};
        for(int i = 1; i <= n ; i++){
            if(findSet(parent,i) == top){
                result[0]++;
            }else{
                result[1]++;
            }
        }
        // System.out.println(Arrays.toString(parent));
        // System.out.println(Math.abs(result[0] - result[1]));
        return Math.abs(result[0] - result[1]);
    }
    private void init (int[] parent, int n){
        for(int i = 0 ; i <= n ; i++){
            parent[i] = i;
        }
    }
    private int findSet(int[] parent , int now){
        if(now == parent[now]){
            return now;
        }
        return parent[now] = findSet(parent,parent[now]);
    }
    private void Union(int[] parent, int a, int b){
        int aParent = findSet(parent,a);
        int bParent = findSet(parent,b);
        if(aParent != bParent){
            parent[aParent] = bParent;
        }
    }
}