[Algorithm][Python]깊이/너비 우선 탐색 알고리즘(DFS/BFS) + 코드

너무 중요한 알고리즘이죠. 대표적인 그래프 탐색 알고리즘인 깊이 우선 탐색, 너비 우선 탐색에 대해서 알아봅시다.

이 그래프를 기본으로 해서 알아보겠습니다.

깊이 우선 탐색(Depth First Search)

먼저 알아볼 것은 깊이 우선 탐색, DFS 입니다. 이번 포스팅에서는 기본 그래프를 트리로 사용하고 있지만 트리에만 사용할 수 있는 것은 아닙니다. DFS는 이름 그대로 그래프를 탐색함에 있어서 깊이를 우선적으로 탐색하는 방법을 말합니다. 

DFS의 탐색 순서입니다. 1 → 2 → 4 → 5 → 3 → 6 → 7 의 순서로 탐색을 진행하는 모습을 확인할 수 있는데요. 저는 DFS를 보면서 호기심이 많은 사람이다 라고 생각했던 기억이 있습니다. 각 노드를 하나의 방이라고 보고 간선이 문이라고 한다면 깊이 우선 탐색은 일단 눈에 보이는 방문을 열고 또 문이 보이면 열고 또 문이 보이면 열다가 문이 없으면 방을 다시 거꾸로 돌아오면서 문이 있나 없나 보다가 문이 있으면 또 문을 여는 과정과 같다는 생각을 했었어요.

 

최초의 깊이 우선 탐색은 스택을 사용해서 구현되었다고 합니다. 다만 저도 그렇지만 최근에는 보통 재귀를 이용해서 구현하는 경우가 많은 것 같아요. 정확한 이유는 아닐 수 있지만 굳이 스택을 만들어서 메모리 관리를 하지 않아도 되고 재귀에 익숙한 사람에 한해서 코드의 가독성이 좋기 때문이 아닐까 합니다. 스택과 재귀 둘 다 사용해서 코드를 작성해보도록 하겠습니다.

 

def dfs_stack(vertices, graph, start):
    visited = [False for _ in range(vertices+1)]
    stack = [start]
    visited[start] = True
    while stack:
        cur_node = stack.pop()
        print(cur_node, end=' ')
        for departure, arrival in graph:
            if cur_node == departure and visited[arrival] == False:
                stack.append(arrival)
                visited[arrival] = True

def dfs_recur(vertices, graph, cur_node, visited):
    if visited[cur_node] == True:
        return
    else:
        print(cur_node, end=' ')
        visited[cur_node] = True
        for departure, arrival in graph:
            if cur_node == departure:
                dfs_recur(vertices, graph, arrival, visited)

vertices = 7
graph = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 6], [3, 7]]

dfs_stack(vertices, graph, 1)
print()
dfs_recur(vertices, graph, 1, [False for _ in range(vertices+1)])

'''
실행 결과:
1 3 7 6 2 5 4 
1 2 4 5 3 6 7
'''

 

어라 실행 결과가 둘이 좀 다르네요. 이거 스택 코드가 잘못된 거 아니에요? 아닙니다. 둘 다 깊이 우선 탐색 코드가 맞으며 잘못된 것은 없습니다. 순서가 다르게 나오는 이유는 스택의 구조 때문인데요. 간단하게 설명을 드리자면 스택은 후입선출의 특징을 갖기 때문입니다. 스택이라는 이름처럼 무언가를 차곡차곡 쌓아올렸다면 당장 바닥부터 빼내는게 아니라 맨 마지막에 쌓아올린 것 부터 하나씩 빼는게 일반적이죠. 그래서 입력으로 사용한 graph에서의 순서를 볼 때 상대적으로 오른쪽에 있던 노드들이 뒤에 입력이 되어서 빠져나올 때는 먼저 빠져나올 뿐입니다. 잘못된 것은 아니에요.

 

너비 우선 탐색(Breadth First Search)

다음으로는 너비 우선 탐색, BFS 입니다. 개인적으로 깊이 우선 탐색보다 너비 우선 탐색을 이해하는게 저는 더 힘들었습니다. 아무래도 이동하는 방향이 간선으로 직접 연결된 방향이 아니라서 시각적인 도움을 DFS에 비해 좀 덜 받았던게 그 이유가 아닐까 생각하고 있는데요. 하지만 익숙해진 뒤에는 어지간하면 그래프 탐색은 다 BFS로 짜는 것 같습니다. 한 번 천천히 가봅시다.

BFS는 DFS에 비하면 움직임이 덜 직관적입니다. 일단 현재 노드에서 갈 수 있는 노드를 다 들러본 다음에 더 이상 갈 곳이 없으면 다음 노드로 이동해서 다시 거기서 갈 수 있는 모든 곳을 갔다가 다른 곳으로 이동하는 것을 반복하는 탐색 방법이에요. 순서로 보면 1 → 2 → 3 → 4 → 5 → 6 → 7 이렇게 되겠네요.

 

너비 우선 탐색은 큐(Queue)를 이용해서 구현하는 편입니다. 다만 다른 언어도 그러는진 모르겠지만 파이썬은 보통 양방향큐(Double Ended Queue, Deque)를 이용해서 구현합니다. 딱히 queue 모듈이 없는 것도 아닌데 다들 deque를 쓰니까 자연스럽게 deque를 쓰게 되는 것 같아요. queue랑 deque 둘 다 한 번 써보죠.

 

from queue import Queue
from collections import deque

def bfs_queue(vertices, graph, start):
    q = Queue()
    q.put(start)
    visited = [False for _ in range(vertices+1)]
    visited[start] = True
    while q.qsize():
        cur_node = q.get()
        print(cur_node, end=' ')
        for departure, arrival in graph:
            if cur_node == departure and visited[arrival] == False:
                q.put(arrival)
                visited[arrival] = True
                
def bfs_deque(vertices, graph, start):
    q = deque([])
    q.append(start)
    visited = [False for _ in range(vertices+1)]
    visited[start] = True
    while q:
        cur_node = q.popleft()
        print(cur_node, end=' ')
        for departure, arrival in graph:
            if cur_node == departure and visited[arrival] == False:
                q.append(arrival)
                visited[arrival] = True
    
vertices = 7
graph = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 6], [3, 7]]

bfs_queue(vertices, graph, 1)
print()
bfs_deque(vertices, graph, 1)

'''
실행 결과:
1 2 3 4 5 6 7
1 2 3 4 5 6 7
'''

 

각각의 장단점

이렇게 그래프 탐색 방법 두가지를 알아 봤습니다. 최단 경로 알고리즘이 그랬듯이 굳이 방법이 두 개 있는 것을 보면 서로가 장단점이 있다는 것을 눈치가 빠른 분들이라면 알아차렸을지도 모르겠어요.

 

DFS가 유리한 경우

DFS는 재귀를 사용할 경우 메모리 관리 면에서 BFS보다 유리한 점이 있습니다. 또, 재귀로 코드를 작성하기 때문에 구현이 BFS에 비해 간단하고 코드가 직관적이겠네요. 굳이 모든 경로를 다 탐색하지 않아도 될 때 약간 유리합니다.

 

BFS가 유리한 경우

BFS는 목표 노드가 시작 노드에 가까이 있을 때(깊이가 얕을 경우) DFS보다 더 유리할 가능성이 있습니다. 이건 좀 개인적인 의견이지만 백준 문제를 풀다 보면 재귀로 코드를 짜면 재귀 깊이 제한이 걸려서 귀찮은 일이 종종 있습니다. BFS는 재귀가 아니라서 그 부분을 신경쓰지 않아도 되니까 더 편할 때가 있었네요.

 

이번에는 좀 불필요한 말을 안하려고 노력해봤습니다. 그 대신 실제로 그래프 탐색을 하는 순서를 GIF로 올려서 좀 더 이해가 편하도록 해봤는데 보기 편하시려나 잘 모르겠네요.