プログラマーLV.3ネットワーク

1.問題リンク

2.解答

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.感じ