백준 2606번 바이러스 - Python

문제 링크 : https://www.acmicpc.net/problem/2606

이번 문제는 BFS를 사용하여 풀면 된다.

BFS

• 너비 우선 탐색(Breadth-First Search)으로 깊게 탐색하기 전에 양 옆으로 넓게 탐색한다. 그래서 시작 정점에서 인접한 노드들을 먼저 탐색 후 멀리 떨어져 있는 노드들을 탐색한다.
• 큐(Queue)를 사용하여 선입선출법(FIFO) 방식으로 탐색한다.

풀이

• 1번 컴퓨터가 바이러스에 걸렸을 때, 1번을 통해 감염된 컴퓨터의 수를 출력하면 된다.
• 입력값은 컴퓨터 수 N, 직접 연결되어있는 간선 수 M과
  이어진 노드의 쌍을 입력한다.
• 이어진 노드들은 딕셔너리 형태로 값을 받아주었다.
• 감염된 컴퓨터 수를 출력해야하므로 1번 컴퓨터(숙주)는 제외시킨다.
• 큐의 성질이 담긴 BFS 함수를 만들어주었다.
• visited[] 라는 빈 리스트를 만들어 방문하지 않은 노드는 추가해준다.(감염된 컴퓨터의 수를 체크하기 위해 / 마지막엔 감염된 노드들만 들어있게 된다.)

해답

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