[백준-파이썬] 2606-바이러스

문제바로가기

1번 컴퓨터에 연결된 모든 컴퓨터의 개수를 세는 문제로 bfs나 dfs를 구현하는 문제이다. 나는 평소에 dfs로 문제풀이를 많이 하기 때문에 이번엔 bfs로 코드를 짜보았다.

from collections import deque
import sys

sys.setrecursionlimit(10**6)

computer = int(sys.stdin.readline())
n_pair = int(sys.stdin.readline())

edge = [[False]*(computer+1) for _ in range(computer+1)]
for _ in range(n_pair):
    i, j = map(int, sys.stdin.readline().split())
    edge[i][j] = True
    edge[j][i] = True
    
visited = [False]*(computer+1)
count = 0
def bfs(n):
    global count
    q = deque([n])
    visited[n] = True
    
    while q:
        cur = q.popleft()
        # print(cur)
        count += 1
        for num in range(1, computer+1):
            if edge[cur][num] == True and not visited[num]:
                q.append(num)
                visited[num] = True

bfs(1)       
print(count-1)

마지막에 count-1을 해주는 이유는 1번 컴퓨터도 개수 집계가 되기 때문이다. 변수를 헷갈리지 않게 유의하며 풀어주도록 하자.