547. Number of Provinces (지방의 수)

n개의 도시가 있습니다. 그 중 일부는 연결되어 있는 반면 일부는 연결되어 있지 않습니다. 도시 a가 도시 b와 직접 연결되어 있고, 도시 b가 도시 c와 직접 연결되어 있다면, 도시 a는 도시 c와 간접적으로 연결되어 있습니다.

지방은 직간접적으로 연결된 도시 그룹이며 그룹 외부의 다른 도시는 없습니다.

i번째 도시와 j번째 도시가 직접 연결되어 있으면 n x n 행렬이 Connected[i][j] = 1이고, 그렇지 않으면 Connected[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] is 1 or 0.
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

 

정답:

public class Solution {
    public int FindCircleNum(int[][] isConnected) 
    {
        int count = 0;
        HashSet<int> h = new HashSet<int>();
        for (int i = 0; i < isConnected.Length; i++)
        {
            if (!h.Contains(i))
            {
                h.Add(i);
                DFS(isConnected, i, h);
                count++;
            }
        }
        
        return count;
    }
    
    private void DFS(int[][] matrix, int i, HashSet<int> h)
    {
        for (int j = 0; j < matrix[i].Length; j++)
        {
            if (i != j && matrix[i][j] == 1 && !h.Contains(j))
            {
                h.Add(j);
                DFS(matrix, j, h);
            }
        }
    }
}

해설: 

도시가 연결되있는지 확인하기 위하여 깊이 우선 탐색을 이용하였고 중복 체크를 위하여 포함되지 않을 때만 DFS함수를 실행하여 해결하였습니다.