백준 2606번: 바이러스 (Python)

 

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

2606번: 바이러스

---

Level: Silver III

Solved By: BFS

 

BFS를 통해서 1번 노드로부터 연결된 모든 노드를 찾는 문제였습니다.

from collections import deque

N = int(input())
M = int(input())

adj = [[] for i in range(0, N + 1)]
visited = [False for _ in range(0, N + 1)]


def bfs(node):
    q = deque([node])
    visited[node] = True
    ret = 0

    while(len(q) != 0):
        now = q.popleft()

        for nxt in adj[now]:
            if(not visited[nxt]):
                visited[nxt] = True
                q.append(nxt)
                ret += 1

    return ret


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

print(bfs(1))