[백준 - Python] 2606. 바이러스 (DFS/BFS)

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

2606번: 바이러스

 

코드

from collections import deque

n = int(input())
con = int(input())
graph = [[] for i in range(n+1)]
for _ in range(con):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)  # 무방향 그래프, graph[a], graph[b]에 동시에 연결 정보를 저장해야 한다

visited = [False] * (n+1)

cnt = 0
queue = deque([1])
visited[1] = True

while queue:
    v = queue.popleft()
    cnt += 1
    for i in graph[v]:
        if not visited[i]:
            queue.append(i)
            visited[i] = True

print(cnt-1)

 

1번 컴퓨터와 연결된 컴퓨터의 개수를 구하는 문제이다.

1번 컴퓨터를 시작 노드로 해서 연결된 컴퓨터를 탐색하면서 개수를 카운팅 해주면 된다.

 

탐색하는 방식으로는 DFS / BFS, 둘 중 뭘 써도 괜찮겠지만,

일반적인 경우에 BFS가 DFS보다 수행시간이 좋은 편이라고 배워서

BFS로 풀어보았다.

 

코드를 짜면서 한 가지 유의할 점은 연결되어 있는 노드 쌍을 그래프 리스트에 저장할 때,

각각의 노드에 연결된 노드를 각각 저장해 주어야 한다는 점이다.