[Python/파이썬] 프로그래머스 네트워크

프로그래머스

코드

from collections import deque

def bfs(visited, computers, n, start):
    q = deque([start])
    
    while q:
        now = q.popleft()
        for i in range(n):
            if computers[now][i] == 1 and not visited[i]:
                q.append(i)
                visited[i] = True
        
def solution(n, computers):
    answer = 0
    visited = [False] * n
    q = deque([])
    
    for i in range(n):
        if not visited[i]:
            visited[i] = True
            bfs(visited, computers, n, i)
            answer += 1
    return answer

컴퓨터를 0번부터 탐색하는데 BFS로 같은 네트워크에 연결된 컴퓨터들을 탐색하며 방문한 컴퓨터들은 visited란 배열에 방문했다고 체크해준다. 이미 방문한 네트워크에 속한 컴퓨터라면 solution 안의 for문에서 본인 순서가 되어도 이미 visited[i]의 값이 True일 것이므로 그냥 지나간다. 따라서 bfs가 실행되는 횟수가 네트워크의 개수이다.