프로그래머스 - 네트워크 [python]

해답 및 풀이

from collections import deque

def solution(n, computers):
    """
    n: 컴퓨터(노드) 개수
    computers: n x n 인접행렬 (computers[i][j] == 1 → i와 j가 연결)
    return: 네트워크(연결 요소) 개수
    """
    visited = [False] * n  # 각 노드를 방문했는지 표시
    networks = 0           # 발견한 네트워크(연결 요소) 개수

  
    def bfs(start):
        """start 노드에서 시작해 연결된 모든 노드를 한 번에 방문한다."""
        q = deque([start])
        visited[start] = True

        while q:
            cur = q.popleft()
            # cur과 연결된 모든 노드(next)를 확인
            for nxt in range(n):
                # 자기 자신이 아니고, 간선이 있으며, 아직 방문 전이면 방문
                if nxt != cur and computers[cur][nxt] == 1 and not visited[nxt]:
                    visited[nxt] = True
                    q.append(nxt)

    # 모든 노드를 훑으며 아직 방문하지 않았다면 -> 새로운 네트워크 시작점
    for i in range(n):
        if not visited[i]:
            bfs(i)
            networks += 1

    return networks

bfs는 꽤나 익숙하지만
아직은 입출력이 없는 프로그래머스형식의 문제에서의 표현이 아직 익숙하지 않아 선뜻 나오지 않고 있다.