[파이썬] 단계별 백준 문제 풀기 - 2606 DFS와 BFS (바이러스)

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

 

---

<<소스코드>>

n = int(input()) #컴퓨터의 개수
m = int(input()) #직접 연결되어있는 컴퓨터 쌍의 수

graph = {}  #노드들의 인접 리스트를 저장할 공간
virus_list = [] # 감염된 컴퓨터들을 저장할 공간

for i in range(1, n+1):  # 컴퓨터 수 만큼 빈 리스트 생성(1~n)후 for문 반복
    graph[i] = [] 		 # 각 컴퓨터는 리스트를 가짐

for i in range(m):       # 입력 받은 노드들의 인접 리스트 생성
    a,b = map(int, input().split()) #a,b는 주어진 인접 컴퓨터의 번호 쌍
    graph[a].append(b) # [a] 컴퓨터에 b 추가, [b] 컴퓨터에 a 추가 (a-b는 서로 인접했으므로)
    graph[b].append(a)


# 시작 컴퓨터(1번)가 방문한 컴퓨터는 모두 감염되므로 인접 컴퓨터를 모두 감염시키는 함수 생성
def infect_virus(ad_graph, virus_start):
    queue = [virus_start] #queue에는 시작 노드(1번 컴퓨터)만 있음                    
    while queue: #queue가 빌때까지 while문 반복                            
        current_node = queue.pop() #현재의 노드를 queue에서 제거
        if current_node not in virus_list: #만약 현재 노드가 바이러스 리스트에 없다면 감염리스트에 추가
            virus_list.append(current_node)   # 방문한 컴퓨터 감염됨
        for ad_node in ad_graph[current_node]: #현재의 노드의 인접 노드들을 for문으로 하나씩 체크
            if ad_node not in virus_list: #감염리스트에 없으면 큐에 추가 
                queue.append(ad_node)     #큐에 추가되면, while문이 참이므로 반복, 인접컴퓨터를 다시 체크하기 시작
    return                                    #큐가 비면 while문이 종료되고 함수 return                    

infect_virus(graph, 1) #virus_start = 1번 컴퓨터
print(len(virus_list)-1) # 바이러스 시작 컴퓨터를 제외한 나머지 길이 구하기

 

<<결과값>>

7
6
1 2
2 3
1 5
5 2
5 6
4 7

4

---

한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 BFS 방식(너비우선탐색)으로 문제를 해결했다.

BFS는 인접한 노드를 먼저 방문하는데, 인접한 노드 중 방문하지 않은 모든 노드들을 일단 저장해두고, 가장 처음에 넣은 노드를 꺼내서 탐색한다. 즉 처음에 넣은 노드를 처음 꺼내주는거니까 큐를 이용하면 된다.

 

큐를 구현하기에 앞서, 주어진 리스트를 graph: 딕셔너리 안에 인접노드들을 리스트로 만들어주었다! 

그리고 각 그래프마다 빈 리스트를 만들어주고,

 

BFS를 이용한 함수를 만들어줬다. 

시작노드를 큐에 넣어주고, 큐에서 시작노드를 빼서 virus_list에 추가한다(visted, 방문했으니 감염). 그리고 시작노드와 인접한 노드들을 for문으로 순차 탐색한다. 인접노드들도 바이러스에 감염되었을테니, 바이러스 리스트에 없으면 큐에 추가한다. ----> (반복) -----> 큐에 저장되어있는 인접 노드들을 pop으로 순차적으로 꺼내서 current_node로 정의 -> 바이러스 리스트 추가 -> 인접노드 탐색

 

반복하다가 이제 큐가 비었으면(인접노드를 다 탐색했다면) 함수를 마친다. 

 

 

- BFS: 너비 우선 탐색, queue를 이용하여 지금 위치에서 근접한 곳들을 모두 queue에 넣고 탐색함

- DFS: 깊이 우선 탐색, 루트 노드에서 시작해 최대한 깊이 탐색하고, 더 이상 탐색할 곳이 없다면 이전 정점으로 돌아감

 

 

BFS/DFS는 시간이 나면 구체적인 특징과 큐/스택의 구현 방법을 더 공부해봐야겠다!!!

알고리즘에서 중요한 개념이니 꼭 짚고 넘어갈 것