leetcode link

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.

---

547. 도의 개수

여기에는 n개의 도시가 있습니다. 일부는 서로 연결되어 있고, 일부는 연결되어 있지 않습니다. 만약 도시 a가 도시 b와 직접 연결되어 있고, 도시 b가 도시 c와 직접 연결되어 있다면, 도시 a는 도시 c와 간접적으로 연결되어 있다고 볼 수 있습니다.

도(省) 는 직접적이거나 간접적으로 연결된 도시의 집합으로, 그 집합 외의 다른 도시는 포함되지 않습니다.

n x n 행렬 isConnected가 주어지며, 여기서 isConnected[i][j] = 1은 i번째 도시와 j번째 도시가 직접 연결되어 있다는 것을 나타내고, isConnected[i][j] = 0은 그렇지 않음을 나타냅니다.

모든 도의 수를 반환하세요.

예시 1:

• 입력: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
• 출력: 2

예시 2:

• 입력: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
• 출력: 3

제약 사항:

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j]는 1 또는 0입니다.
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

Solution

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length; // 도시의 수
        boolean[] visited = new boolean[n]; // 도시의 방문 여부를 추적하는 배열

        int province = 0; // 도의 수
        for (int i = 0; i < n; i++) {
            if (!visited[i]) { // 방문하지 않은 도시를 찾으면
                dfs(isConnected, visited, i); // DFS로 도의 모든 도시 방문
                province++; // 새로운 도 발견
            }
        }

        return province;
    }

    private void dfs(int[][] isConnected, boolean[] visited, int i) {
        int n = isConnected.length;
        visited[i] = true; // 현재 도시를 방문했음을 표시
        for (int j = 0; j < n; j++) {
            if (!visited[j] && isConnected[i][j] == 1) { // 직접 연결된 아직 방문하지 않은 도시가 있는 경우
                dfs(isConnected, visited, j); // 연결된 다음 도시로 이동
            }
        }
    }
}