BFS(너비 우선 탐색)과 DFS(깊이 우선 탐색)은 트리의 노드를 스캔하는 대표적인 방법이다. 각 방식은 큐와 스택을 이용해 구현하게 되는데, Swift에서 스택은 배열로 구현하면 되지만 큐를 구현하는 것이 문제다. C++처럼 STL로 기본 자료구조들을 제공하고 있지 않기 때문이다... 😢

일단 기초부터

🎄트리

트리는 데이터 사이의 계층 관계를 표현하는 자료구조로, 아래 그림과 같이 노드(동그라미, 정점이라고도 함)와 가지(동그라미 간의 연결선, 간선이라고도 함)로 구성된다. 각 노드는 가지를 통해 다른 노드와 연결될 수 있다.

간단하게 노드는 마을 하나하나를, 가지는 마을을 서로 연결하는 다리라고 생각하면 된다.

트리의 가장 위쪽에 있는 노드를 루트(root)라고 하며, 루트는 트리 하나에 한 개만 존재한다. 또한, 루트에서 얼마나 멀리 떨어져 있는가를 나타내는 것이 레벨(level)이다.
가장 위쪽에 있는 루트의 레벨은 0이고, 가지가 한 단계씩 아래로 뻗어 내려갈 때마다 레벨이 1 증가한다.

👀 너비 우선 탐색 (Breadth-First Search)

너비 우선 탐색은 동일 레벨 전체를 탐색한 뒤 다음 레벨로 나아가는 탐색 방법이다. 깊이 우선 탐색이 레벨 끝까지 깊게 파고 내려갔다 다시 돌아오는 것과 달리 루트에서 가까운 노드들부터 우선으로 탐색하게 되는 차이가 있다.

위 그림과 같이 탐색하게 되며, 루트와 가까운 노드부터 탐색해 나간다는 특성 때문에 주로 최단 거리를 구하는 문제에서 유용하게 쓰인다.

🔍 BFS와 큐

BFS를 구현하기 위해 왜 큐가 필요한지, 간단한 미로 탐색 예제를 통해 살펴보자.

파란색 칸은 이동할 수 있는, 주황색 칸은 이동할 수 없는 벽이다. (0, 0) 칸에서 출발하여 탈출구인 초록색 칸(3, 5)에 도달하는 것이 목표이다. BFS로 탐색해 나가는 일련의 과정을 보며 큐 자료구조가 쓰이는 방법을 살펴보자.

아직 방문하지 않은 이동 가능한 길을 상하좌우를 시계방향으로 확인하며, 거리 확인을 위해 방문 표시는 본인의 칸 방문 표시 + 1로 할 것이다.

1. (0, 0)에서 시작, (0, 0)을 push하고, 방문 표시를 한다.
   

2. 큐에서 pop하여 (0, 0)이 현재 대상 노드가 되고 주변을 탐색한다.
   

3. 아직 방문하지 않았으면서 이동할 수 있는 칸(1, 0)이 있다면 큐에 push하고 방문 표시를 한다.
   

4. (0, 0)에서 탐색을 마쳤으므로, 다음 탐색할 노드를 큐에서 pop하여 현재 대상 노드로 두고 주변 탐색을 진행한다.
   (그림에는 오른쪽과 아래만 탐색하지만, bfs에서 위쪽도 일단 탐색한다. 다만 이미 방문한 칸이기 때문에 큐에 추가하지 않는다.)
   

5. 아직 방문하지 않았으며 이동 가능한 칸 (1, 1)과 (2, 0)이 큐에 push되고 방문 표시를 남긴다.
   

6. (0, 0)에서 탐색을 마쳤으므로, 다음 탐색할 노드를 큐에서 pop하여 현재 대상 노드로 두고 주변 탐색을 진행한다.
   (역시 상하좌우를 모두 탐색하지만, 벽인 (0, 1)과 (2, 1) 그리고 이미 방문한 (1, 0)은 큐에 추가하지 않게 된다.)
   

7. 아직 방문하지 않았으며 이동할 수 있는 칸인 (1, 2)가 큐에 push되고 방문 표시를 남긴다.
   

8. (1, 1)에서 탐색을 마쳤으므로, 다음 탐색할 노드를 pop하여 현재 대상 노드로 두고 주변 탐색을 진행한다.
   (역시 상하좌우를 모두 탐색한다.)
   

9. 아직 방문하지 않았으며 이동할 수 있는 칸인 (3, 0)이 큐에 push되고 방문 표시를 남긴다.
   

...

이러한 일련의 과정을 거쳐 초록색 탈출구 칸까지 도착하게 되며, 미로에 표시한 값을 통해 최단 거리가 얼마인지 얻을 수 있다.

요약

BFS는 다음과 같은 과정을 거쳐 탐색한다.

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다.
2. 큐에서 원소를 꺼내어 그 칸에 인접한(문제의 기준마다 다를 수 있음.) 칸에 대해 탐색을 진행한다.
3. 탐색이란, 해당 칸을 이전에 방문했거나 방문할 수 없는 조건(미로 문제에서는 벽에 해당)이라면 아무것도 하지 않고, 처음으로 방문한 방문 가능한 칸이라면 방문 표시를 남기고 해당 칸을 큐에 삽입한다.
4. 큐가 빌 때까지 혹은 탈출구에 도착할 때까지 2번을 반복한다.

모든 칸이 큐에 한 번씩만 들어가므로, 시간복잡도는 칸의 수와 같은 O(N)이다.

구현 시 주의점

처음 BFS를 구현할 때 자주 하는 실수로

1. 시작점, 다음 탐색 노드 등을 큐에 넣을 때 방문했다는 표시를 하기.
2. 탐색할 노드의 좌표가 인덱스 범위를 벗어났는지 체크하기.

등이 있다. BFS가 시간 초과가 나거나 - 메모리 초과가 난다면 1번을 제대로 처리하지 못해 같은 칸이 계속 큐에 다시 들어가지는 않는지 확인해 보자. 만약 인덱스 오류가 난다면, 2번을 다시 점검해 보자.

큐의 선입 선출 방식 그대로 BFS가 작동하는 것을 볼 수 있다. 이처럼 BFS를 구현하는 데 큐가 필수적인데, Swift에는 기본 제공 큐가 없으므로 다른 방법을 통해 BFS를 구현해야 한다.

다음 글에서는 Swift로 BFS를 구현하는 세 가지 방법을 소개한다!

References

바킹독 블로그 - BFS
KKS227 블로그 - 너비 우선 탐색
Do it! 자료구조와 함께 배우는 알고리즘 입문 (파이썬 편)