[백준] 2606번 바이러스 파이썬 정답 코드

2606번: 바이러스

---

1. 문제 내용

 

 

2. 접근 방식

• 1번 컴퓨터와 연결된 노드들을 탐색한다.

깊이 우선 탐색과 너비 우선 탐색 모두 사용할 수 있다. 그러나 너비 우선 탐색 코드가 가장 먼저 떠올라서 너비 우선 탐색으로 코드를 작성하였다.

 

 

3. 정답 코드

from collections import deque

def bfs(v):
    visited[v] = True
    queue = deque([v])

    while queue:
        n = queue.popleft()

        for i in data[n]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)

    return sum(visited) - 1 # 1은 카운트 되면 안 되기 때문에 -1한다


n = int(input())
c = int(input())

data = [[] for _ in range(n + 1)]
for _ in range(c):
    x, y = map(int, input().split())
    data[x].append(y)
    data[y].append(x)

visited = [False] * (n + 1)

print(bfs(1))