[프로그래머스] lv3. 네트워크 [#Union-Find]

 

 

---

1. 문제 출처

---

 

 

 

 

---

2. 설계

---

 

- 노드가 연결된 모양세를 보고 같은 네트워크를 가진 뭉텅이는 몇 개가 있는지 세주는 문제이다.

- 즉, 부모가 같은 무리가 몇 개인지 세주는 것이다.

- 그래서 union-find 풀면 될 것 같았다.

 

 

 

 

 

---

3. 전체 코드

---

//union - find
class Solution {
    static int[] p;
    static int[] order;
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        
        p = new int[n+1];//1부터 시작
        order = new int[n+1];
        setP(n);
        
        int rowLength = computers.length;
        int colLength = computers[0].length;
        
        //i = 컴퓨터 n번
        for(int i=0;i<rowLength;i++){
            for(int j=0;j<colLength;j++){
                if(i==j) continue;
                if(computers[i][j]==1){
                    
                    if(findP(i+1)==findP(j+1)) continue;
                    connectP(i+1, j+1);
                }
            }
        }
        
        //네트워크 수 산정
        int[] count = new int[n+1];
        for(int i=1;i<=n;i++){
            count[findP(p[i])]++; //여기 조심 p[i]만 하면 안됨
        }
        
        for(int i=1;i<=n;i++){
            if(count[i]!=0) answer++;
        }
        
        
        return answer;
    }
    
    public static void connectP(int c1, int c2){
        
        int c1_p = findP(c1);
        int c2_p = findP(c2);
        
        if(order[c1_p]>=order[c2_p]){
            order[c1_p]++;
            p[c2_p]=c1_p;
        }else{
            order[c2_p]++;
            p[c1_p]=c2_p;
        }
    }
    
    public static int findP(int child){
        if(p[child]==child) return child;
        return findP(p[child]);
    }
    
    public static void setP(int n){
        for(int i=1;i<=n;i++){
            p[i]=i;
        }
    }
}

 

 

주의할 점

//네트워크 수 산정
int[] count = new int[n+1];
for(int i=1;i<=n;i++){
	count[findP(p[i])]++; //여기 조심 p[i]만 하면 안됨
}

count[p[i]]만 했다면 

 

입력값 〉 4, [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 1, 0, 1]]
기댓값 〉 1

 

해당 테스트 케이스에서 틀렸을 것이다.

유니온 과정을 거칠 때 최종 부모의 부모의 값만 바꿔주지 부모가 걸쳐있는 자식까지 바뀐 부모로 바꿔주지 않기 때문이다.

때문에 자식들의 찐 부모를 찾아 count를 ++해주어야 한다.