[프로그래머스] 전력망을 둘로 나누기 (Union-Find) - Java

 

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

프로그래머스

 

입력: n=전력망의 수 wires배열 = 연결정보

위 그림처럼 [1,3]의 의미는 1번과 3번을 연결하는 것이며 임의의 연결을 제거하고 둘로 나눠진 전력망을 빼서 가장 작은 수를 출력하는 것이다. 그림에서는 전력망을 분리해 6개 3개로 나뉘어졌고 6-3은 3이기에 정답은 3이 된다.

 

풀이

이 문제를 보자마자 전력망을 연결시키기에 연결이라는 단어에 
union-find로 풀어야겠다고 생각했다.
단순하게 전력망 연결정보인 wires배열의 값들을
하나씩 건너뛰고(전력망 끊고) union 시켰다.
union시키는 기준은 작은값을 기준으로.

자른것을 기준으로 반쪽은 lt변수 반쪽은 rt변수로 연결된 전력망의 수를
각각 구하고 빼면서 어렵지 않게 풀 수 있다.

[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]

[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]
.
.
.

import java.util.*;
class Solution {
    static private int[] unf;
    public static int Find(int v){
        if(v==unf[v]) return v;
        else return unf[v]=Find(unf[v]);
    }
    //결합
    public static void Union(int a, int b){
        int fa=Find(a);
        int fb=Find(b);
        if(fa!=fb) {
            //unf[fa]=fb;
            if(fa>fb) unf[fa] = fb;
            else unf[fb] = fa;
    	}
	}
    //전력망 끊은 나머지 값
    public static int getRemainder(int n) {
    	int lt=0, rt=0;
    	for(int i=1; i<=n; i++) 
    		if(Find(unf[i])==1) lt++;
    	rt = n-lt;
    	return Math.abs(lt-rt);
    }
        
    public int solution(int n, int[][] wires) {
        int answer = n;
        for(int i=0;i<wires.length;i++){
            unf = new int[n+1];
            for(int p=0;p<=n;p++)unf[p]=p;
            for(int j=0; j<wires.length; j++) {
        		if(i==j) continue;//매번 하나씩 선 끊어봄
                Union(wires[j][0],wires[j][1]);
            }
            int tmp = getRemainder(n);
            //System.out.println(Arrays.toString(unf) + " tmp : "+tmp);
            answer = Math.min(answer,tmp);
        }
        
        return answer;
    }
}