[Graph - DFS, Medium] Number of Provinces

https://leetcode.com/problems/number-of-provinces/description/?envType=study-plan-v2&envId=leetcode-75

문제를 보면 딱 떠오르는 아이디어는, input 배열을 순회하면서 만나는 모든 노드에 체크해주는 것

첫 순회 시 이어지는 모든 노드에 대해 visited 체크를 하고 나면,
다음번에는 visited=false인 부분으로 동일한 작업을 수행하고 지방 카운트를 +1하면 되겠다.

이 작업을 반복하면 총 지방 수를 알 수 있을 듯

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int count = 0;
        boolean[] visited = new boolean[isConnected.length];

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

    private void dfs(boolean[] visited, int current, int[][] isConnected) {
        visited[current] = true;
        for (int i=0; i<isConnected.length; i++) {
            if (isConnected[current][i] == 1 && !visited[i]) {
                dfs(visited, i, isConnected);
            }
        }
    }
}

참고: 이 문제는 Union-find로 풀 수 있는 전형적인 문제인 듯 - 공부