[백준] 2606번 바이러스 - DFS와 BFS(Python)

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

2606번: 바이러스

 

사용 알고리즘

그래프 탐색을 할 때 사용되는 알고리즘은 DFS(깊이 우선 탐색법)와 BFS(너비 우선 탐색법)이다.

 

DFS(깊이 우선 탐색법)

그래프 탐색 방식의 일종으로, 트리/그래프의 갈림길에서 막다른 길이 나올 때 까지 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트를 탐색하는 방식이다.

BFS(너비 우선 탐색법)

그래프 탐색 방식의 일종으로, 트리/그래프의 갈림길에 연결되어 있는 모든 길을 한번씩 탐색 한 뒤 다시 연결되어 있는 길을 넓게 탐색하는 방식이다

풀이

컴퓨터 1번이 감염 되었을 때 1번 컴퓨터를 통해 웜 바이러스에 감염 되는 컴퓨터의 수를 찾는 문제이므로, DFS/BFS를 구현한 뒤 1번 노드부터 탐색을 시작하면 되는 문제이다.

 

네트워크 연결은 n*n의 리스트를 생성하여 표현하였다. 예를들어 컴퓨터 1과 2가 연결되어있다면 arr[1][2], arr[2][1]을 1로 표시하고 그렇지 않다면 0으로 표시하였다. 또, check 리스트를 생성하여 각 노드가 이전에 참조된 적이 있는지 판단하는 용도로 사용하였다.

DFS 구현

n = int(input())   #컴퓨터 수

m = int(input())  #컴퓨터 쌍의 수

arr = [[0 for col in range(101)]for row in range(101)]

check =[0]*101

global cnt

cnt = 0

 

def DFS(v):

    global cnt

    check[v] = 1

    for i in range(1,n+1):

        if (check[i]!=1 and arr[v][i]):

            cnt+=1

            DFS(i)

필자는 재귀함수를 이용하여 DFS를 구현하였다. DFS함수의 매개변수인 v는 현재 v번째 노드와 연결된 노드를 탐색한다는 의미이며, if 문에서 v번째 노드가 i번째 노드와 연결되어있을때, i번째 노드가 이전에 탐색된 적이 있는가를 판단하고 그렇지 않다면 해당 i번째 노드로 이동하여 탐색을 계속하게 된다. 이때 전역변수 cnt의 값을 1올려주어 감염된 컴퓨터 대수를 파악한다.

 

BFS 구현

n = int(input())   #컴퓨터 수

m = int(input())  #컴퓨터 쌍의 수

arr = [[0 for col in range(101)]for row in range(101)]

check =[0]*101

global cnt

cnt = 0

 

def BFS(v):

    global cnt

    queue = [v]

    check[v] = 1

    while queue:

        v = queue[0]

        del queue[0]

        for i in range(1,n+1):

            if (check[i] != 1 and arr[v][i]):

                queue.append(i)

                cnt+=1

                check[i] = 1

BFS는 queue를 사용하여 구현하였다. 너비를 우선적으로 탐색하며 만나는 노드들이 이전에 참조 된 적이 없으면 queue에 추가하고 cnt를 1올려준다. while문에서 탐색이 완료된 노드는  queue에서 제거하며, 남아있는 원소가 없을 때 까지 탐색을 이어나가므로 노드들을 빠짐없이 탐색하게 된다.

 

Python

n = int(input()) #컴퓨터 수

m = int(input()) #

arr = [[0 for col in range(101)]for row in range(101)]

check =[0]*101

global cnt

cnt = 0

def DFS(v):

    global cnt

    check[v] = 1

    for i in range(1,n+1):

        if (check[i]!=1 and arr[v][i]):

            cnt+=1

            DFS(i)

def BFS(v):

    global cnt

    queue = [v]

    check[v] = 1

    while queue:

        v = queue[0]

        del queue[0]

        for i in range(1,n+1):

            if (check[i] != 1 and arr[v][i]):

                queue.append(i)

                cnt+=1

                check[i] = 1

#배열 초기화            

for i in range(m):

    tmp1, tmp2 = map(int,input().split())

    arr[tmp1][tmp2] = 1

    arr[tmp2][tmp1] = 1

BFS(1) #or DFS(1)

print(cnt)

 

DFS와 BFS 두가지를 모두 구현하였는데 탐색 순서만 다를 뿐, 같은 그래프 탐색 이론에 속하므로 둘 중 어느 이론을 사용하더라도 문제를 해결 할 수있다.