네트워크 | 알고달레

프로그래머스의 네트워크 문제를 함께 풀어보도록 하겠습니다.

문제

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
computer[i][i]는 항상 1입니다.

예제

Input:
  n: 3
  computers: [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
Output: 2

Input:
  n: 3
  computers: [[1, 1, 0], [1, 1, 1], [0, 1, 1]]
Output: 1

풀이 1

문제를 풀기 전에 주어진 첫 번째 예제에서 네트워크의 수가 왜 2인지를 먼저 같이 생각해볼까요?

주어진 이차원 배열을 좀 더 알아보기 쉽게 여러 줄에 표시해보겠습니다.

[1, 1, 0]
[1, 1, 0]
[0, 0, 1]

그리고 이 것을 시각화해 보면 다음과 같은 모습이 될 것입니다.

0 - 1 👉 첫 번째 네트워크
2     👉 두 번째 네트워크

각 컴퓨터를 정점(Vertex, Node)으로 보고 컴퓨터 간의 연결을 간선(Edge)으로 보면 이 문제는 전형적인 그래프(Graph) 문제라는 것을 알 수 있는데요. computers 입력 배열은 자연스럽게 그래프를 표현하는 인접 행렬(adjacency matrix)이 되고요.

각 컴퓨터를 출발점으로 해서 그래프를 탐색을 하다가 더 이상 연결된 컴퓨터가 없으면 네트워크를 하나를 발견한 것이라고 볼 수 있겠습니다.

여기서 주의할 부분은 한 번 방문한 컴퓨터는 절대 재방문해서는 안 된다는 것입니다. 그렇지 않으면 네트워크 안에서 무한 루프에 빠질 수 있기 때문입니다. 예를 들어, 위의 첫 번째 네트워크를 보시면 컴퓨터 0과 컴퓨터 1 사이를 계속 왕복할 것입니다.

이럴 때는 집합(Set) 자료구조를 사용하면 효과적으로 재방문을 방지할 수 있습니다. 컴퓨터를 추가하거나 어떤 컴퓨터가 있는지 확인하는데 모두 O(1)의 시간이 걸리기 때문입니다.

그럼 설명드린 깊이 우선 탐색(DFS, Depth First Search) 알고리즘을 재귀 함수를 사용해서 파이썬으로 구현해보겠습니다.

def solution(n, computers):
    count = 0
    visited = set()

    def dfs(node):
        visited.add(node)

        for nei in range(n):
            if nei not in visited and computers[node][nei]:
                dfs(nei)

    for start in range(n):
        if start not in visited:
            dfs(start)
            count += 1

    return count

첫 번째 예제를 기준으로 위 코드를 돌려보면 다음과 같은 구조로 재귀 함수가 실행이 되어 결과로 2를 반환하게 될 것 입니다.

start = 0
dfs(0)
    node = 0
    visited = {0}
    nei = 0
    nei = 1
    dfs(1)
        node = 1
        visited = {0, 1}
        nei = 0
        nei = 1
        nei = 2
    nei = 2
count = 1

start = 1

start = 2
dfs(2)
    node = 2
    visited = {0, 1, 2}
    nei = 0
    nei = 1
    nei = 2
count = 2

n을 컴퓨터의 개수라고 했을 때, 이 풀이의 시간 복잡도는 O(n^2)입니다. 중복 방문을 막고 있기 때문에 재귀 함수가 각 컴퓨터를 상대로 딱 한 번씩만 호출되는 것을 볼 수 있고요. 각 재귀 함수 안에서 n번의 반복이 일어나는 루프가 돌기 때문입니다.

반면에 공간 복잡도는 집합에는 n개의 컴퓨터를 저장해야 하기 때문에 O(n)이 됩니다.

풀이 2

조금 더 생각을 해보면 메모리 사용량을 좀 줄일 수 있지 않을까요? 문제의 제한 사항 중에서 computer[i][i]은 항상 1이 저장되어 있다고 했으니까, 그 위치에 컴퓨터 방문 여부를 저장한는 것입니다. 그러면 굳이 추가적으로 집합 자료구조를 사용하지 않고도 입력 배열만으로 이 문제를 해결할 수 있을 것 같습니다.

컴퓨터를 방문했을 경우, 그 위치에 1 대신에 0을 저장하고, 탐색 전에 computer[i][i]를 확인하도록 코드를 수정해보겠습니다.

def solution(n, computers):
    count = 0

    def dfs(node):
        computers[node][node] = 0

        for nei in range(n):
            if computers[nei][nei] and computers[node][nei]:
                dfs(nei)

    for start in range(n):
        if computers[start][start]:
            dfs(start)
            count += 1

    return count

그런데 이렇게 메모리 최적화를 해주면 과연 공간 복잡도가 향상될까요? 아쉽게도 재귀 함수의 호출 스택의 깊이가 최대 n이 되므로 빅오 계신법을 따르는 공간 복잡도에는 변화가 없습니다.

그럼에도 불구하고 코드가 좀 더 간단해지고, 추가 자료구조를 쓰지 않기 때문에 더 좋은 풀이이라고 볼 수 있겠습니다.

풀이 3

깊이 우선 탐색은 재귀 알고리즘 대신에 스택(Stack) 자료구조를 사용해서 많이 구현하죠? 반복 알고리즘을 사용하면 스택 오버플로우(Stack Overflow) 문제를 피할 수 있기 때문에 실무에서 선호합니다.

그럼 동일한 알고리즘을 스택을 사용해서 반복 알고리즘으로 구현해보겠습니다.

def solution(n, computers):
    count = 0

    for start in range(n):
        if computers[start][start]:
            count += 1
            stack = [start]
            while stack:
                node = stack.pop()
                computers[node][node] = 0
                for nei in range(n):
                    if computers[nei][nei] and computers[node][nei]:
                        stack.append(nei)

    return count

최대 n 개의 컴퓨터가 스택에 저장될 수있기 때문에 역시 공간 복잡도는 O(n)으로 유지됩니다.

마치면서

이 문제는 그래프 탐색의 기초를 다치는데 매우 도움이 되는 문제라고 생각합니다. 코딩 테스트에서 그래프를 어떻게 다루는지에 대해서 좀 더 공부하고 싶으시다면 관련 게시물을 참고 바랄께요.