[Python] 백준 2606 - 바이러스

백준 2606 - 바이러스 [SILVER 3]

https://www.acmicpc.net/problem/2606

 

N개의 컴퓨터와 N개의 연관 관계가 있다.

1번 컴퓨터가 바이러스에 감염되었을 때, 1번 컴퓨터로 인해 몇 개의 컴퓨터가 바이러스에 감염되었는가?

BFS

매우 간단한 BFS 문제입니다.

특별한 조건 없이, 1번 컴퓨터로 인해 감염된 컴퓨터의 개수만 구하면 됩니다.

컴퓨터를 N+1의 리스트로 만들고, 연관 관계를 상호간으로 리스트에 넣어준 뒤

1번부터 시작하여 BFS로 순회하면서, 방문한 노드에 대한 정보를 기록하여

1번을 제외한, 방문한 적 있는 컴퓨터의 갯수만 나타내면 됩니다.

정답 코드

import sys

input = sys.stdin.readline

N = int(input())
route = [[] for _ in range(N+1)]

for i in range(int(input())):
    s, e = map(int, input().split())

    route[s].append(e)
    route[e].append(s)

Q = route[1].copy()
visited = [0] * (N+1)
visited[1] = 1

while Q:
    n = Q.pop(0)
    if not visited[n]:
        visited[n] = 1
        Q.extend(route[n])

print(sum(visited[2:]))

결과는 다음과 같다.

메모리	시간	코드 길이
31120KB	40ms	391B