백준 2606 바이러스 - 파이썬

 

 

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

2606번: 바이러스

 

 

 

스탠다드한 그래프 탐색 문제이다.

 

 

 

- DFS 풀이

컴퓨터(노드) 간의 연결 정보는 graph라는 이차원 배열에 저장했다. 

graph[n]에는 n번 컴퓨터와 연결된 컴퓨터들을 저장한다.

예를 들어 1번 컴퓨터가 2, 4번 컴퓨터와 연결되어 있다면 graph[1] = [2, 4]가 된다.

 

그다음 그래프에 컴퓨터들 간의 연결관계를 input 받아서 저장한다.

1번과 2번 컴퓨터가 서로 연결되어 있다면 graph[1]에도 2를 append 해주고, graph[2]에도 1을 append 해줘야 한다.

 

 

 

그래프 탐색을 할 때 이미 체크한 컴퓨터를 또 확인하고 또 확인하면 시간 초과가 난다.

그래서 체크 여부를 저장해주기 위해 checked 배열을 만들어준다.

보통 int 배열로 선언하고 1, 0으로 쓰는 경우가 많은데, 나는 취향껏 boolean 배열로 만들었다.

1번 컴퓨터는 처음부터 감염되어 있을 거니까 True로 초기화했다.

 

 

 

 

이제 본격적인 감염 전파를 시작할 것이다.

stack이라는 스택 리스트에 저장할 컴퓨터는 방금 막 감염된 컴퓨터들이다.

시작할 때는 감염원인 1만 담겨 있다.

이 컴퓨터와 연결된 컴퓨터들을 감염시켜야 한다.

 

 

while문을 돌려보자.

 

일단 최근에 감염된 컴퓨터를 pop 한다. 이름은 curr라고 붙였다.

curr와 연결된 컴퓨터들을 담은 리스트가 graph[curr]이니까 그 안에 담겨있는 컴퓨터들을 탐색한다.

 

curr과 연결된 next 컴퓨터 중에 아직 체크를 안 한 컴퓨터가 있다면 checked[next]를 True로 갱신해 준다.

방금 막 감염됐다. stack에 append 해주면 된다.

 

stack 무언가가 담겨있는 한 계속 탐색을 한다.

연결된 모든 컴퓨터가 감염이 되었다면 stack이 비게 되고, while문이 break 될 것이다.

 

 

 

checked에 체크된 컴퓨터, 즉 감염된 컴퓨터의 수는 checked에서 True의 개수를 카운트해주면 알 수 있다.

다만, 1번 컴퓨터는 원래부터 감염되어 있었으므로 답에서 1을 빼야 한다.

 

 

 

 

N = int(input()) # 컴퓨터의 개수
graph = [[] for _ in range(N+1)] # graph[n]에는 n번 컴퓨터와 연결된 컴퓨터들을 저장

# 그래프에 컴퓨터들 간의 연결 관계 저장
for _ in range(int(input())): 
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)


# 체크 여부 저장할 배열
checked = [False] * (N+1)
checked[1] = True

# 1번 컴퓨터에서 바이러스 시작
stack = [1]

# DFS
while stack: # 더 이상 확인할 컴퓨터가 없으면 break
    curr = stack.pop() # 최근에 감염된 컴퓨터부터 확인

    for next in graph[curr]: # curr 번 컴퓨터와 연결된 컴퓨터들 순회
        if not checked[next]: # 아직 체크 안한 컴퓨터라면
            checked[next] = True # 체크
            stack.append(next) # 이 컴퓨터랑 연결된 컴퓨터도 체크할 거얌

print(checked.count(True)-1) # 1번 컴퓨터 빼고 감염된 컴퓨터의 수 출력

 

 

 

이 풀이가 DFS인 이유는 stack에서 pop 해가며 다음 컴퓨터를 탐색하는 방법 이어서다.

 

1번 컴퓨터에 2, 4번이 연결되어 있는 경우라고 치면,

1번 > 2번 > 2번에 연결된 뭐시기 > 뭐시기에 연결된 저시기 순으로 탐색하게 되기 때문이다.

저시기의 저시기까지 끝까지 탐색을 하면 그제서야 4번 컴퓨터를 탐색하게 된다.

 

BFS의 경우에는 1번 >> 2번 > 4번 >> 2번에 연결된 뭐시기들 > 4번에 연결된 뭐시기들 ... 이런 순서로 탐색하게 된다.

 

 

 

사실 어떻게 탐색해도 상관없는 문제이다.

이런 경우에는 스택 자료형을 사용하는 DFS 풀이가 덜 귀찮지만 공부하기 위해서 BFS로 풀어봐도 좋다.

 

 

 

 

 

- BFS 풀이

 

from collections import deque

N = int(input())
graph = [[] for _ in range(N+1)]

for _ in range(int(input())):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)


visited = [False] * (N+1)
visited[1] = True

queue = deque([1])

while queue:
    curr = queue.popleft()

    for next in graph[curr]:
        if not visited[next]:
            visited[next] = True
            queue.append(next)

print(visited.count(True)-1)

 

 

DFS 풀이와 똑같다.

 

스택이 아닌 덱을 사용했단 것만 다르다.

사실 그냥 queue를 쓰면 되는데, 파이썬에서는 큐보다 덱이 빠르다. 물론 큐를 써도 이문제는 통과된다.

뒤에서 pop 해서 쓰는 스택과 달리 앞에서 popleft 해서 탐색하게 돼서 1번 컴퓨터와 연결된 차수 순서대로 탐색할 수 있게 되겠다.

 

 

 

좀 더 오버하자면 연결 관계를 확인하는 문제니까 유니온 파인드를 이용해서도 풀 수 있다.