문제 링크 : https://www.acmicpc.net/problem/2606
이번 문제는 BFS를 사용하여 풀면 된다.
BFS
- 너비 우선 탐색(Breadth-First Search)으로 깊게 탐색하기 전에 양 옆으로 넓게 탐색한다. 그래서 시작 정점에서 인접한 노드들을 먼저 탐색 후 멀리 떨어져 있는 노드들을 탐색한다.
- 큐(Queue)를 사용하여 선입선출법(FIFO) 방식으로 탐색한다.
from sys import stdin
read = stdin.readline
dic={} # {1:{a,b}}
for i in range(int(read())): # 7
dic[i+1] = set() # 인덱스는 0부터 시작이니까 +1 해줌
for j in range(int(read())): # 6
a, b = map(int,read().split()) # [1,2][2,3][1,5][5,2][5,6][4,7]
dic[a].add(b) #양방향 성질
dic[b].add(a)
def bfs(start):
queue = [start]
while queue:
for i in dic[queue.pop(0)]: # 큐(선입선출법) 첫번째꺼 지워주고 마지막에 넣어준다
if i not in visited: # visited에 값이 없으면
visited.append(i)
queue.append(i)
visited = [] #[2,5,1,3,6]
bfs(1) # = start = 1
print(len(visited)-1) # 1은 숫주 그 자체이므로 감염된 컴퓨터 수를 구하기 위해 -1