백준 2606번 바이러스 | python | bfs

문제

링크

풀이

그래프 정보를 인접리스트에 잘 담고, 1을 루트 노드로 하여 bfs()를 수행한다. 이 때 다른 노드를 방문할 때 마다 cnt를 1 더해준다.

bfs() 실행이 끝나면 cnt 값을 출력해 주면 된다. bfs()를 모든 노드에 대해서 돌릴 필요없이 1을 루트 노드로 하여 한 번만 수행해주면 되므로 매우 쉽게 풀이할 수 있다.

import sys
from collections import deque

input = sys.stdin.readline

c = int(input().strip())
e = int(input().strip())

arr = [[] for _ in range(c + 1)]
visited = [0] * (c + 1)
for _ in range(e):
    a, b = map(int, input().strip().split())
    arr[a].append(b)
    arr[b].append(a)


def bfs():
    q = deque()
    q.append(1)
    visited[1] = 1
    cnt = 0
    while q:
        n = q.popleft()
        cnt += 1
        for i in arr[n]:
            if not visited[i]:
                q.append(i)
                visited[i] = 1
    return cnt


print(bfs() - 1)