탐색 알고리즘 – DFS와 BFS

여러분은 미로 찾기를 하다 막다른 길에 다다라 되돌아가며 길을 찾아보신 경험이 있으신가요? 우리가 미로에서 길을 찾는 것과 유사한 방식으로 컴퓨터는 그래프를 탐색할 수 있습니다. 그래프의 탐색을 통해서 컴퓨터는 원하는 정보도 탐색할 수 있고, 그래프 자체의 성질도 파악할 할 수 있습니다. 이번 글에서는 그래프 탐색을 위한 알고리즘 중 가장 기본적인 두 종류의 알고리즘, 깊이 우선 탐색DFS, Depth First Search과 너비 우선 탐색BFS, Breadth First Search에 관해서 설명하고자 합니다.

여기서 그래프란 정점Vertice과 간선Edge으로 구성된 것으로, 여러 정점을 간선들이 연결하는 형태의 자료 구조를 말합니다. 정점과 간선이 거미집 같은 형태의 구조로 되어 있는 것이죠. 깊이 우선 탐색은 그래프를 말 그대로 ‘깊이’의 관점에서 탐색하는 방식입니다. 시작 정점에서 간선을 따라 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없는 막다른 곳일 경우 옆으로 이동하는 방식으로 탐색이 진행됩니다. 그림 1을 살펴보면, 맨 위의 정점부터 시작하여 먼저 왼쪽 가지로 내려가 최대한 깊게 탐색을 진행하고, 이후 옆 가지를 탐색하는 것을 확인할 수 있습니다.

너비 우선 탐색은 깊이 우선 탐색과 달리 ‘너비’에 초점을 둔 탐색 방식입니다. 즉, 최대한 넓게 인접한 정점을 모두 탐색하고 나서 더 이상 갈 수 없을 때 아래로 이동합니다. 그림 1을 보면 맨 위 정점에서 시작하여 인접한 정점을 모두 살피고 나서 아래로 내려가 다음 깊이의 정점들을 탐색한다는 것을 확인할 수 있습니다.

비슷한 듯 다른 두 알고리즘, 구현 방식에는 큰 차이가 존재합니다. DFS의 경우 주로 스택자료 구조를 통해 구현합니다. 스택이란 ‘후입선출’ 방식으로 나중에 들어온 정점이 먼저 나가는 방식의 자료 구조입니다. DFS는 깊이에 따라 탐색을 진행하면서 탐색한 각 정점이 순서대로 스택에 들어옵니다. 들어온 정점은 제거되면서 그 자식 정점, 즉 아래로 인접한 정점들이 스택에 들어옵니다. 그림 2를 보면, 2번째 단계에서 3번째로 넘어갈 때, B가 제거되며 그 자식 정점인 D와 F가 들어오는 것을 확인할 수 있습니다. 이런 식으로 나중에 들어온 정점을 제거하며 그 자식 정점들을 추가하는 방식으로 스택을 이용하면, DFS를 구현할 수 있습니다.

반면 BFS는 ‘선입선출’ 방식의 자료 구조인 큐를 통해 구현합니다. 그림 2를 보면, 시작 지점인 A가 큐에 들어오고, 다음으로 A가 제거되며 그 자식인 B, C가 들어옵니다. 그리고 B가 제거되며 그 자식들인 D와 F가 들어옵니다. 이렇게 먼저 들어온 정점을 제거하며 그 정점의 자식들을 큐에 넣는 방식으로 큐를 이용하면, BFS를 구현할 수 있습니다.

이러한 DFS와 BFS를 이용하여 우리는 최단 거리 문제를 포함한 다양한 문제를 해결할 수 있습니다. 시작 정점에서 출발하여 BFS를 통해 얻은 종료 지점의 정점이 큐에 들어올 때까지 거리를 체크한다면, 최단 거리를 쉽게 구할 수 있습니다. 또한, 우리는 DFS와 BFS를 통해 그래프의 성질도 파악할 수 있습니다. 예를 들어 1부터 5까지의 정점이 있을 때 1부터 탐색을 수행했는데, 1부터 4까지만 탐색이 되었고 5는 탐색하지 못했다고 해 봅시다. 그러면 우리는 이 그래프가 1~4의 연결 성분과 5의 연결 성분, 두 성분이 있음을 알 수 있습니다. 이 밖에도 DFS와 BFS의 활용은 굉장히 다양합니다.

이처럼 DFS와 BFS는 간단한 알고리즘이지만 그 활용도가 높고, 다른 복잡한 알고리즘에서도 활용되는 기본 알고리즘입니다. 관련 분야에 관심이 있는 학생들은 DFS와 BFS를 간단하게 코딩으로 구현해 보는 것은 어떨까요?

[참고자료]

DFS와 BFS : https://devyuseon.github.io/algorithm/dfs-and-bfs/

글 / 무은재학부 21학번 27기 알리미 김현준