프로그래머스: 네트워크

문제

코딩테스트 연습 - 네트워크

 

문제 풀이

 네트워크의 정보가 주어질 때, 연결 정보를 통해 몇 개의 네트워크가 존재하는지 판단하는 문제이다. BFS로 풀 수 있는 문제이며 다음과 같이 풀 수 있다.

 

예제 #1

• 노드 1은 2번과 연결되어 있다.
• 노드 2는 1번과 연결되어 있다.
• 노드 3은 다른 노드와 연결되어 있지 않다.
• 따라서 네트워크의 개수는 2이다.

예제 #2

•  노드 1, 2, 3은 서로 연결되어 있다.
• 따라서 네트워크 개수는 1이다.

 이와 같은 연결에 따라 네트워크 개수를 체크하기 위해서는, 각 노드를 시작으로 하여 탐색을 진행하고 `visited`를 체크하여 추가적으로 방문 가능한 경로가 있는지 여부를 확인하면 된다. 해당 방식으로 탐색하게 되면, `예제 #1`의 경우 노드 1, 노드 2를 시작으로 탐색할 경우 하나의 경로에 대한 탐색이기에 경우의 수가 1 추가되고, 노드 3을 시작으로 탐색할 경우에 하나의 경로에 대한 탐색이 가능하므로 총 2개의 네트워크를 찾을 수 있다.

 

코드

from collections import deque


def bfs(computers, visited, start):
    q = deque()
    q.append(start)
    while q:
        node = q.popleft()
        if not visited[node]:
            visited[node] = 1

        for connect_node in range(len(computers)):
            if not visited[connect_node] and computers[node][connect_node]:
                q.append(connect_node)


def solution(n, computers):
    answer = 0
    visited = [0] * n
    while not all(visited):
        for node in range(n):
            if not visited[node]:
                bfs(computers, visited, node)
                answer += 1
    return answer