[LeetCode] 547 Number of Provinces

Description

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Example 1:

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Example 2:

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

Constraints:

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] is 1 or 0.
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

---

풀이

도시들이 몇개로 연결되어있는지(그룹 도시의 수)를 출력시키는 문제이다.

인접행렬로 도시의 연결을 나타낸다.

도시가 어떻게 연결되었는지 알기 위하여 recursive DFS를 사용하였다.

dfs 함수는 연결된 도시들을 찾기 때문에 연결되지 않은 떨어진 도시들은 찾을 수 없다. 그래서 위의 findCircleNum 함수에서 연결되지 않은 도시들도 찾을 수 있도록 도시의 개수만큼 반복시켰다.

fincCircleNum
방문하지 않은 도시일 경우, 도시의 개수를 1 증가시키고 dfs 함수를 실행하여 연결된 도시들을 탐색한다.

dfs
방문한 도시를 true로 바꾸고, 방문하지 않은 연결된 도시를 찾아서 dfs 함수를 다시 실행한다.

---

코드

class Solution {

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

    public static void dfs(int startPoint, int[][] isConnected, boolean[] visited) {
        visited[startPoint] = true;
        for (int j = 0; j < isConnected.length; j++) {
            if (startPoint == j) {
                continue;
            }
            if (isConnected[startPoint][j] == 1 && visited[j] == false) {
                dfs(j, isConnected, visited);
            }
        }
    }
}