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

문제 이해

한 컴퓨터가 바이러스에 걸리면 네트워크에 연결되어 있는 컴퓨터도 바이러스에 걸린다고 한다.
1번 컴퓨터가 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 전염된 컴퓨터의 수를 출력한다.

1번 컴퓨터가 속한 네트워크 상에 몇 대의 컴퓨터가 있는지 파악하는 문제이다.

아이디어

BFS를 통해 풀어보았다.
우선 입력값으로 주어지는 네트워크를 생성한다. 컴퓨터 번호는 1번부터 시작하는 것에 유의한다.
BFS를 돌면서 방문한 컴퓨터들을 리스트에 담고, 1번 컴퓨터 본인은 제외해야 하므로 (방문한 컴퓨터의 길이-1)을 리턴해준다.

코드

# https://www.acmicpc.net/problem/2606
from collections import deque
n = int(input())
m = int(input())
network = [[] for i in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    network[a].append(b)
    network[b].append(a)

def bfs(network, start):
    need_visit = deque([start])
    visited = []
    while need_visit:
        node = need_visit.popleft()
        if node not in visited:
            visited.append(node)
            need_visit.extend(network[node])
    return len(visited)-1

print(bfs(network, 1))