[Python]Baekjoon 2606번: 바이러스(BFS)

1. 문제

 

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

2606번: 바이러스

 

1번 컴퓨터와 연결된 컴퓨터가 몇 개인지를 구하는 문제이다.

 

첫 그래프 탐색 문제이다.

 

2. 풀이

우선 BFS를 이용하여 풀이하여 보자.

 

파이썬에서 queue를 구현할 때는 list가 아닌 deque를 활용하는데 그 이유는 시간 복잡도 측면에서 deque가 유리하기 때문이다.

 

리스트를 활용하여 큐를 구현할 수는 있지만, 큐의 연산을 수행할 때(리스트의 앞쪽에서 요소를 삭제하거나 추가할 때) O(n)의 시간이 소요된다. 이는 리스트의 특성상 요소를 삭제하거나 추가할 때 해당 요소 뒤의 모든 요소를 이동시켜야 하기 때문이다.

반면에 collections.deque는 이중 연결 리스트로 구현되어 있어 큐의 양쪽 끝에서 빠르게 요소를 추가하거나 삭제할 수 있다. 이를 통해 큐의 연산인 enqueue(삽입)와 dequeue(삭제)를 모두 O(1)의 시간복잡도로 수행할 수 있다.

 

문제 해결 과정을 생각해 보면,

 

우선, 그래프와 방문 여부를 표시할 리스트를 초기화하고

그래프 정보를 입력받을 때, a 컴퓨터에 b를 넣고, b 컴퓨터에 a를 넣어서 서로 연결되도록 한다(양방향).

 

이후에 BFS를 구현하게 되는데, Q = deque([1])로, 첫 번째 컴퓨터에 대해 덱을 만든다.

 

Q에 값이 있는 동안 while문을 돌며, now에 큐에서 원소를 뽑아 저장한다.(now는 지금 보고 있는 컴퓨터를 가리킨다)

 

 다음은 for 문을 돌며 graph[now]를 통해 now번 컴퓨터에 연결되어 있는 컴퓨터(node)를 방문한다.

 

만약에 방문하지 않은 컴퓨터라면 Q에 해당 컴퓨터를 추가하고, 방문 처리를 한다.

 

이 과정을 Q에 더 이상 원소가 남지 않을 때까지 반복하면 되고,

 

visited 리스트에 1의 개수를 카운트하면 연결된 컴퓨터의 개수를 알 수 있다.

3. 코드

from collections import deque

computer = int(input())

network = int(input())

graph = [[] for _ in range(computer+1)]

visited = [0] * (computer+1)

for i in range (network):

    a, b = map(int, input().split())

    graph[a].append(b)

    graph[b].append(a)

   

visited[1] = 1 # 첫 번째 컴퓨터에 방문 표시

Q = deque([1]) # 첫 번째 컴퓨터에 대해 덱을 만든다.

while Q:

    now = Q.popleft()

    for node in graph[now]:

        if visited[node] == 0:

            Q.append(node)

            visited[node]=1

           

print(sum(visited)-1)

 

4. 느낀점

그래프 문제를 처음으로 풀어보았다.

 

역시 혼자서는 접근조차 어려울 정도로 어려운 알고리즘인 것 같다.

 

BFS 알고리즘이 대략적으로 어떻게 구현되는지 이해할 수 있는 문제였다.

 

다음에는 같은 문제를 DFS를 활용하여 해결해 보자.

 

오늘 하루도 쌓였다.