백준 2606번: 바이러스

백준 2606번: 바이러스

아이디어

그냥 그래프 탐색하면서 몇개나 연결됐는지 세면 된다.

코드

from collections import deque

v = int(input())
e = int(input())
graph = [[] for _ in range(v+1)]
visited = [False] * (v+1)
deq = deque()

for _ in range(e):
    v1, v2 = map(int, input().split())
    graph[v1].append(v2)
    graph[v2].append(v1)


def bfs(start, visited):
    visited[start] = True
    deq.append(start)
    cnt = 0
    while deq:
        v = deq.popleft()
        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                deq.append(i)
                cnt += 1
    return cnt


print(bfs(1, visited))

여담

한국정보올림피아드시․도지역본선 > 지역본선 2004 > 초등부 3번 문제라고 한다. 난 초등학생이다.