[Programmers] 네트워크 (with Python / BFS, DFS)

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

문제설명

문제 설명

 

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다.

문제풀이

네트워크의 개수를 return 해야한다. 나는 BFS로 풀었다. 

쉽게 말하면 총 그래프의 구역 수를 세는 문제이다.

Edge로 이어진 네트워크 그룹을 세야하므로,

방문리스트를 만들고 방문하지 않은 모든 노드를 시작으로 BFS를 시행한 다음,

한번의 BFS가 끝날때마다 answer를 1 늘리면 된다.

 

주의할 점은,

백준의 "적록색약"이나 "유기농배추"처럼 이차원 배열에서 구역수를 세는 것이 아닌,

실제 그래프 상에서 구역수를 세는 것이 핵심이다.

굳이 말하면 백준의 "바이러스" 문제와 비슷할 것 같다.

 

코드

from collections import deque

def solution(n, computers):
    answer = 0
    visited = [0] * n
    queue = deque()
    
    def BFS(node):
        queue.append(node)
        visited[node] = 1
        while queue:
            v = queue.popleft()
                
            for nv in range(n):
                if computers[v][nv] == 1 and not visited[nv]:
                    queue.append(nv)
                    visited[nv] = 1
    
    for i in range(n):
        if not visited[i]:
            BFS(i)
            answer += 1
            
    return answer