[백준] 2606 바이러스

문제

• 네트워크 상에 컴퓨터들이 연결되어 있고, 한 컴퓨터가 바이러스에 걸리면 연결된 모든 컴퓨터는 바이러스에 걸리게 된다.
• 네트워크 상의 컴퓨터의 연결 정보가 주어질 때, 1번 컴퓨터를 통해 바이러스에 걸리게 되는 컴퓨터의 수 출력하기
• 1 <= 컴퓨터의 수 <= 100

 

풀이

• BFS로 바이러스를 전파하고, 바이러스에 감염된 컴퓨터의 개수 세기

 

from collections import deque

# 입력 받기
N = int(input())
M = int(input())
networks = [[] for _ in range(N+1)]
for _ in range(M) :
    a, b = map(int, input().split())
    networks[a].append(b)
    networks[b].append(a)

virus = [0] * (N+1)		# 바이러스에 전염되면 1 아니면 0
# 바이러스 전파하기
q = deque([1])
virus[1] = 1
while q :
    now = q.popleft()

    for nxt in networks[now] :
        if virus[nxt] == 0 :
            q.append(nxt)
            virus[nxt] = 1

print(sum(virus)-1)

 

References

• 백준 그래프 탐색