[프로그래머스 Lv.3] 네트워크 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

풀이

deque를 사용한 BFS로 문제를 풀이하였다. 일반적인 BFS 문제를 풀이하는 것처럼 visited라는 배열을 통해 네트워크를 구성할 노드의 방문 여부를 확인하여 전체 노드 순회를 완료하였을 때 몇 개의 네트워크를 생성할 수 있는지 확인하면 된다. 

from collections import deque
def solution(n, computers):
    answer = 0
    
    visited = [0 for _ in range(n)] # 각 노드의 방문 여부를 저장할 배열
    
    d = deque() # BFS를 위한 덱 자료구조
    
    for i in range(n): # 노드 전체를 순회하면서
        if visited[i] == 1: # 이미 방문한 노드는 스킵
            continue
        
        d.append(i) # 방문 안한 노드를 BFS를 위해 덱에 저장
        answer += 1 # 새로운 노드에서 BFS를 시작했다는 것은 새로운 네트워크를 순회하기 시작했다는 것이므로 갯수 증가
        
        while len(d) > 0: # 덱이 빌 때까지
            cur = d.popleft() # 현재 노드

            visited[cur] = 1 # 현재 노드 방문 표시

            for i in range(n): # 현재 노드와 연결된 모든 노드들을 체크
                if cur != i and visited[i] == 0 and computers[cur][i]: # 체크하는 노드가 자기 자신이 아니고, 이미 방문한 노드가 아니고, 연결된 노드인지 확인
                    d.append(i) # 덱에 저장
        
    return answer