프로그래머스 - 네트워크

문제 설명

제한사항 및 입출력

풀이

분리되어있는 그래프가 몇 개인지 찾는 전형적인 그래프 탐색 문제이다.

첫 번째 노드부터 bfs를 돌려서 이미 방문한 노드에 대해서는 visited를 체크하고 한 번의 그래프 탐색이 끝날 때마다 ans를 올려서 풀이해주었다.

내 코드

from collections import deque
    
def solution(n, computers):
    # visited와 ans를 전역에서 관리
    visited = [False] * n
    ans = 0
    
    def bfs(graph, visited, start):
        nonlocal ans
        queue = deque([start])
        visited[start] = True

        while queue:
            x = queue.popleft()
            
            # nx = 노드 번호, e = 간선의 유무
            for nx, e in enumerate(graph[x]):
                if e and not visited[nx]:
                    queue.append(nx)
                    visited[nx] = True
                    
        # 한 번의 bfs(네트워크 탐색)이 끝나면 ans += 1
        ans += 1

        return visited
    
    for i in range(n):
        if not visited[i]:
            visited = bfs(computers, visited, i)
    
    return ans

visited를 전역 배열로 두어서 한 번 방문한 노드는 다시 탐색하지 않는 것이 포인트인 것 같다.

 

시간 복잡도: 그래프가 인접행렬로 주어지기 때문에 O(n^2)이다. 인접 리스트로 주어진다면 연결되어있는 노드만 탐색할 수 있기 때문에 O(v + e)가 되었겠지만 여기서는 인접 행렬로 주어져서 모든 노드를 탐색해야한다.

고찰

union-find를 사용해서 풀이할 수도 있다.

def solution(n, computers):
    # parent[i] = 노드 i의 부모 노드 (초기값은 본인)
    parent = list(range(n))
    rank = [0] * n

    # 부모 노드 찾기
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    # 노드를 하나의 네트워크로 합치기
    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb:
            return
        
        if rank[ra] < rank[rb]:
            parent[ra] = rb
        elif rank[ra] > rank[rb]:
            parent[rb] = ra
        else:
            parent[rb] = ra
            rank[ra] += 1
    
    # 두 노드가 연결되어있다면 union 연산으로 합침
    for i in range(n):
        for j in range(i + 1, n):
            if computers[i][j] == 1:
                union(i, j)

    # 같은 네트워크라면 find(i)의 값이 같으므로 집합으로 중복 제거 후 길이 반환 = 서로 다른 네트워크의 수
    return len({find(i) for i in range(n)})

애초에 이름 자체가 분리 집합인 친구이기 때문에,,, 이런 문제를 보면 union-find가 꼭 같이 생각나는 것 같다. 

시간 복잡도는 결국 모든 노드에 대해서 연결되어있는지 찾아야하기 때문에 O(n^2)으로 동일하다.