[프로그래머스-Lv3] 네트워크 / Python

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

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
compters = [list(map(int, input().split())) for _ in range(n)]


def bfs(n, computers, v, visited):
    queue = deque()
    queue.append(v)
    visited[v] = True

    while queue:
        x = queue.popleft()
        for i in range(len(computers[x])):
            if i == x:
                continue
            if visited[i] == False and computers[x][i] == 1:
                visited[i] = True
                queue.append(i)


def solution(n, computers):
    answer = 0
    visited = [False] * n

    for i in range(n):
        if visited[i] == False:
            bfs(n, computers, i, visited)
            answer += 1

    return answer


print(solution(n, compters))

 

해설

BFS로 해결할 수 있는 문제였다.

컴퓨터의 개수만큼 visited 리스트를 False로 초기화해 만들어준다.

visited에서 False인 값의 인덱스는 BFS로 처리가 안된 것이므로 BFS를 실행한다. 그러면 해당 정점과 연결되어 있는 모든 정점들이 방문처리가 되고, 네트워크가 하나 늘어나는 것이다.