문제

문제링크

접근

• 연결된 모든 곳을 탐색한다는 점에서 dfs를 떠올렸다.
• union-find와 같이 아예 집합을 다르게 구분을 해야한다는 생각을 잠깐 했다가, 출발점으로 구분을 하면 되겠다 생각하였다.
• 그래서 dfs를 제어 반복문 안에서 호출하여 해결하였다.

소스 코드

class Main {
    public static void main(String[] args) throws Exception {
        int[][] computers = { { 1, 1, 0 }, { 1, 1, 0 }, { 0, 0, 1 } };
        int n = 3;

        Solution sol = new Solution();
        System.out.println("result : " + sol.solution(n, computers));
    }
}

class Solution {
    boolean[] isConnected;
    int length;

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

        for (int i = 0; i < length; i++) {
            if (!isConnected[i]) {
                dfs(i, computers);
                answer++;
            }
        }
        return answer;
    }

    void dfs(int i, int[][] computers) {
        isConnected[i] = true;

        for (int j = 0; j < length; j++) {
            if (computers[i][j] == 1 && !isConnected[j]) {
                dfs(j, computers);
            }
        }
    }
}