프로그래머스 LV.3 네트워크

프로그래머스 LV.3 네트워크

1. 문제 링크

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

코딩테스트 연습 - 네트워크

 

2. 문제 해결에 대한 아이디어

1. 이 문제는 Disjoint-Set(Union-Find) 로 풀 수 있다.
2. 이러한 유형은 두 가지 함수에 대해서 알고 있으면 쉽게 풀 수 있다.
   - findParent : 해당 함수의 최종 부모 찾기
   - union : 부모가 다른 두 노드를 동일한 부모를 갖도록 만들기
3. findParent에서 아래 내용은 경로 단축을 적용한 것이다.
   - return parent[x] = findParent(parent[x]);
   - 많은 문제에서 위와 같이 구현하면 시간 단축이 된다.
   - 일부 문제는 시간이 오히려 더 걸리는 경우도 존재했다.
4. Disjoint-Set 문제는 거의 비슷한 패턴으로 구현하면 해결된다.
   1. 자신을 부모로 갖는 배열 만들기(중요)
   2. findParent, union 함수 구현
   3. 문제의 조건에 맞춰서 findParent, union 사용

 

3. 코드

class Solution {
    static int[] parent;

    public int solution(int n, int[][] computers) {
        int answer = computers.length;

        /**
         * 1. 자신을 부모로 갖는 배열 만들기
         */
        parent = new int[computers.length];
        
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
        
        /**
         * 연결관계에 있는 두 노드를 하나로 합치기
         */
        for (int i = 0; i < computers.length; i++) {
            for (int j = 0; j < computers[i].length; j++) {
                if (computers[i][j] == 1) {
                    if (findParent(i) != findParent(j)) {
                        union(i, j);
                        answer--;
                    }
                }
            }
        }
        return answer;
    }

    /**
     * 2. 자신의 부모 찾기
     */
    static int findParent(int x) {
        if (parent[x] != x) {
            return parent[x] = findParent(parent[x]);
        }

        return x;
    }
    /**
     * 3. 두 노드의 부모를 한 쪽의 부모로 맞추기
     */
    static void union(int a, int b) {
        a = findParent(a);
        b = findParent(b);

        if (a < b)
            parent[b] = a;
        else
            parent[a] = b;
    }

}

4. 채점 결과

5. 느낀 점

1. 프로그래머스에서는 DFS/BFS로 구분되어 있었으나, Disjoint-Set(Union-Find)으로도 풀 수 있다.
2. Disjoint-Set(Union-Find)는 대개 비슷한 패턴으로 해결할 수 있다.