[알고리즘] 백준 2606 파이썬 - 바이러스(DFS 풀이)

 

2606번: 바이러스

문제

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

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

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

 

문제풀이

#DFS방식
import sys 
input = sys.stdin.inputline
dic={}
n= int(input()
for i in range(n):
    dic[i+1] = set()
#01
for j in range(int(input())):
    a, b = map(int,input().split())
    dic[a].add(b)
    dic[b].add(a)
#02
def dfs(start, dic):
    for i in dic[start]:
        if i not in visited:
            visited.append(i)
            dfs(i, dic)
visited = []
#03
dfs(1, dic)
print(len(visited)-1)

- dic이라는 딕셔너리를 정의해준다.

- 1부터 입력받은 n까지 dic에 할당해준다.

- #01: for문을 통해서 dic에 각각 a,b를 추가해준다.

- #02: dfs함수를 정의하여 start값과 dic값을 입력받는다.

          dic[start]의 값이 visited 리스트에 없으면 추가해준다.

         이후 그전  i 값을 start값으로하여 다시 dfs함수를 반복한다.

- #03 : 최종적으로 visited 함수에는 1번 컴퓨터와 연결된 리스트가 완성되었고,

           이는 1번 컴퓨터를 포함하고 있기에 문제가 원하는 답인 "len(visited)-1"을 출력해준다.

 

 

 

 

- DFS와 BFS의 차이

1. DFS (Depth-First Search) :  깊이 우선 탐색

출처&nbsp;https://developer-mac.tistory.com/64

위의 시각자료와 같이 최대한 깊은 곳까지 내려갔다가

더 이상 내려갈 곳이 없으면 옆으로 탐색하는 것을 DFS라고 한다.

구현은 스택 또는 재귀함수로 한다.

위의 문제도 dfs 함수에 dfs 함수를 넣는 재귀함수 방식으로 풀었다.

 

2. BFS (Breadth-First Search) : 너비 우선 탐색

출처&nbsp;https://developer-mac.tistory.com/64

위의 시각자료와 같이 최대한 정점과 가까운 곳으 먼저 탐색하는 것을 BFS라고 한다.

구현은 큐를 이용해서 한다.

 

- DFS와 BFS의 활용

1) 모든 정점을 방문하는 것이 핵심인 문제

단순히 모든 정점을 방문하는 문제는 DFS와 BFS 모두 사용이 가능하기에,

사용하기 편리한 것을 사용하면 된다. 

​

2) 경로의 특징을 저장해둬야 하는 문제

1 부터 10까지 이동 중 동일한 값을 추가하면 안 되는 등 경로의 특징을 저장해야할 때는

DFS 방식을 사용해야 한다.

 

3) 최단거리 구해야 하는 문제

지뢰를 피하여 최단거리를 구해야 하는 경우 등은 BFS가 유리하다.

너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾아가기에 초반에 발생하는 답이

최단거리이기 때문이다. 반대로 DFS는 그렇지 않을 수 있기에 비효율적이다.