Number of Provinces

LeetCode의 547번째 문제인 Number of Provinces를 함께 풀어보도록 하겠습니다.

문제

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

직접 또는 간접적으로 연결된 도시의 그룹을 도(province)라고 합니다. 도시들의 연결 정보를 나타내는 n x n 행렬 isConnected가 주어집니다. isConnected[i][j] = 1이면 i번째 도시와 j번째 도시가 직접 연결되어 있음을 의미하고, isConnected[i][j] = 0이면 그렇지 않음을 의미합니다.

전체 province의 총 개수를 반환하시오.

예제

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

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

풀이 1

주어진 행렬에서 몇 개의 도(province)가 있는지 알아내려면, 서로 연결되어 있는 도시의 그룹을 찾아야합니다. 극단적인 예로, 도시가 하나도 연결되어 있지 않다면 각 도시 자체가 도가 되어 도의 개수가 n이 되고, 반대로 모든 도시가 연결되어 있다면 도의 개수는 1이 될 것입니다.

도시의 그룹 하나를 찾으려면 그 안에 연결되어 있는 도시를 모두 찾아야하는데요. 여기서 도시를 정점(vertex)이라고 보고, 도시 사이의 연결을 간선(edge)라고 보면, 우리는 그래프(graph) 탐색으로 이 문제에 접근할 수 있습니다.

각각의 도시 그룹이 얼마나 큰지는 해당 그룹 안에 모든 도시를 탐색할 때 까지는 알 수 없겠죠? 따라서, 주어진 그래프를 깊이 우선 탐색하든 너비 우선 탐색하는 지는 별로 중요하지 않습니다.

대신 중요한 것은 탐색할 때 한 번 방문한 도시는 다시 방문하면 안 된다는 것인데요. 집합(set) 자료 구조를 이용하여 방문한 도시를 쉽게 추적할 수 있습니다.

그럼 첫 번째 예제를 가지고 중복 방문에 주의하면서 깊이 우선 탐색을 같이 해볼까요?

우선 도시 0과 연결된 모든 도시를 탐색해보겠습니다. 도시 0과 도시 0은 당연히 연결되어 있고, 우리는 적어도 도가 1개는 있다는 것을 알 수 있습니다.

   0  1  2
0 [1, 1, 0] 👈
   👆
1 [1, 1, 0]
2 [0, 0, 1]

도의 개수: 0 + 1 = 1
방문한 도시: {} + {0} = {0}

도시 0과 도시 1은 연결되어 있으므로, 도시 1은 도시 0과 같은 그룹에 들어갑니다.

   0  1  2
0 [1, 1, 0] 👈
      👆
1 [1, 1, 0]
2 [0, 0, 1]

도의 개수: 1
방문한 도시: {0} + {1} = {0, 1}

깊이 우선 탐색을 위해서 잠시 도시 0과 연결된 도시에 대한 탐색을 멈추고, 도시 1과 연결된 도시를 먼저 탐색하겠습니다. 도시 1과 연결된 도시 0과 도시 1, 두 개인데 모두 도시 0을 탐색할 때 이미 방문했기 때문에 건너 뜁니다. 도시 1과 도시 2는 연결되어 있지 않습니다.

   0  1  2
0 [1, 1, 0] 👈
1 [1, 1, 0] 👈
         👆
2 [0, 0, 1]

도의 개수: 1
방문한 도시: {0, 1}

도시 1과 연결된 도시에 대한 탐색을 마쳤으니, 도시 0으로 다시 돌아와서 멈췄던 탐색을 재개합니다. 도시 0과 도시 2는 연결되어 있지 않습니다.

   0  1  2
0 [1, 1, 0] 👈
         👆
1 [1, 1, 0]
2 [0, 0, 1]

도의 개수: 1
방문한 도시: {0, 1}

도시 1은 방금 방문하였으니 건너 뛰고, 도시 2와 연결된 도시를 탐색하겠습니다. 도시 2는 자기 자신 외에 다른 도시와는 연결되어 있지 않으므로, 혼자서 하나의 도를 이룹니다.

   0  1  2
0 [1, 1, 0]
1 [1, 1, 0]
2 [0, 0, 1] 👈
         👆

도의 개수: 1 + 1 = 2
방문한 도시: {0, 1} + {2} = {0, 1, 2}

이 깊이 우선 탐색 알고리즘을 재귀 함수를 이용하여 파이썬으로 구현해보겠습니다.

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def dfs(start):
            visited.add(start)
            for end, connected in enumerate(isConnected[start]):
                if end not in visited and connected == 1:
                    dfs(end)

        cnt = 0
        visited = set()
        for start in range(len(isConnected)):
            if start not in visited:
                cnt += 1
                dfs(start)

        return cnt

n을 도시의 개수라고 했을 때, 이 풀이의 시간 복잡도는 행렬의 크기와 비례해서 O(n^2)이 됩니다. 공간 복잡도는 세트가 n에 비례하는 메모리를 추가적으로 사용하므로 O(n)이 됩니다.

풀이 2

입력으로 주어진 행렬 내의 값을 변경할 수 있다면, 굳이 세트와 같은 추가 자료구조가 필요하지 않을 것입니다. 입력 행렬 내에서 탐색을 마친 연결에 대한 0으로 변경하면, 해당 연결을 다시 고려되는 것을 방지할 수 있기 때문입니다. 예를 들어, 도시 x을 방문했다면, isConnected[x][x]을 0으로 변경하는 것입니다.

그럼 입력 행렬을 변경하면서 첫 번째 예제를 가지고 깊이 우선 탐색을 해볼까요?

도시 0과 도시 0은 당연히 연결되어 있으므로, isConnected[0][0]을 0으로 변경합니다.

   0  1  2
0 [0, 1, 0] 👈
   👆
1 [1, 1, 0]
2 [0, 0, 1]

도의 개수: 0 + 1 = 1

도시 0과 도시 1은 연결되어 있으므로, isConnected[1][1]을 0으로 변경합니다.

   0  1  2
0 [0, 1, 0] 👈
      👆
1 [1, 0, 0]
2 [0, 0, 1]

도의 개수: 1

깊이 우선 탐색을 위해서 잠시 도시 0과 연결된 도시에 대한 탐색을 멈추고, 도시 1과 연결된 도시를 먼저 탐색해야 합니다. isConnected[0][0]과 isConnected[1][1]이 모두 0이기 때문에, 바로 도시 2로 건너 띌 수 있습니다. 도시 1과 도시 2는 연결되어 있지 않으므로, 다시 도시 0으로 돌아와 멈췄던 탐색을 재개할 수 있습니다.

   0  1  2
0 [0, 1, 0] 👈
1 [1, 0, 0] 👈
         👆
2 [0, 0, 1]

도의 개수: 1

도시 0과 도시 2는 연결되어 있지 않습니다.

   0  1  2
0 [0, 1, 0] 👈
         👆
1 [1, 0, 0]
2 [0, 0, 1]

도의 개수: 1

isConnected[1][1]은 0이니 이미 방문했다는 뜻이므로 건너 뛰고, 도시 2와 연결된 도시를 탐색하기 위해서 isConnected[2][2]를 0으로 변경하겠습니다. 도시 2는 자기 자신 외에 다른 도시와는 연결되어 있지 않으므로, 혼자서 하나의 도를 이룹니다.

   0  1  2
0 [0, 1, 0]
1 [1, 0, 0]
2 [0, 0, 0] 👈
         👆

도의 개수: 1 + 1 = 2

이 살짝 변형된 깊이 우선 탐색 알고리즘을 파이썬으로 구현해볼까요?

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def dfs(start):
            isConnected[start][start] = 0
            for end, connected in enumerate(isConnected[start]):
                if isConnected[end][end] == 1 and connected == 1:
                    dfs(end)

        cnt = 0
        for start in range(len(isConnected)):
            if isConnected[start][start] == 1:
                cnt += 1
                dfs(start)

        return cnt

이 풀이의 시간 복잡도와 공간 복잡도는 이전 풀이와 동일합니다. 세트 자료구조를 사용하지 않으므로 공간 복잡도가 향상될 거라고 생각할 수 있는데, 재귀 알고리즘은 공간 복잡도는 호출 스택의 깊이에 비례하므로 여전히 O(n)입니다.

풀이 3: 스택

그래프의 깊이 우선 탐색은 스택을 이용하면 반복 알고리즘으로도 구현할 수 있습니다.

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        cnt = 0
        for start in range(len(isConnected)):
            if isConnected[start][start] == 1:
                cnt += 1
                stack = [start]
                while stack:
                    start = stack.pop()
                    isConnected[start][start] = 0
                    for end, connected in enumerate(isConnected[start]):
                        if isConnected[end][end] == 1 and connected == 1:
                            stack.append(end)
        return cnt

마치면서

코딩 시험에서 그래프(graph)을 다루는 유형의 문제에서는 이 문제가 가장 기본이 된다고 볼 수 있는데요. 본 문제를 통해 기본기를 잘 닦아놓으셔서 같은 유형의 좀 더 어려운 문제를 풀 때 큰 도움이 되었으면 좋겠습니다.

이 문제가 너무 쉬우셨다면 비슷하지만 좀 더 어려운 문제인 Number of Islands도 풀어보시라고 추천드립니다. 코딩 테스트에서 그래프 자료구조를 어떻게 다루는지에 대해서 더 공부하고 싶으시다면 관련 게시물을 참고 바랄께요.