DFS — 깊이 우선 탐색 알고리즘 설명

깊이 우선 탐색(DFS)은 트리나 그래프를 탐색할 때, 한 경로를 가능한 한 끝까지 따라간 뒤 되돌아오는 알고리즘입니다. 쉽게 말해 DFS는 계속 더 깊이 들어가다가 더 이상 갈 곳이 없으면, 다른 갈림길이 있던 마지막 지점으로 돌아옵니다.

하나만 기억한다면 이것입니다. DFS는 "깊게 들어가고, 막히면 되돌아온다"입니다.

깊이 우선 탐색이 하는 일

DFS는 트리에도 사용할 수 있고, 일반 그래프에도 사용할 수 있습니다. 하나의 노드에서 시작해서 아직 방문하지 않은 이웃으로 계속 이동합니다. 더 이상 방문하지 않은 이웃이 없는 노드에 도달하면, 이전 노드로 되돌아가서 거기서 다시 탐색을 이어갑니다.

이 되돌아가는 과정이 DFS의 핵심 특징입니다. 재귀 구현에서는 호출 스택이 이 역할을 자동으로 처리합니다. 반복 구현에서는 명시적인 스택이 같은 역할을 합니다.

DFS 방문 순서가 달라질 수 있는 이유

DFS에는 하나의 고정된 방문 순서만 있는 것이 아닙니다. 정확한 순서는 이웃 노드를 어떤 순서로 확인하느냐에 따라 달라집니다.

예를 들어 어떤 노드의 이웃이 $B$와 $C$라면, $B$를 먼저 방문할 때와 $C$를 먼저 방문할 때 DFS 순서는 달라질 수 있습니다. 그래도 두 경우 모두 DFS입니다. 규칙은 같기 때문입니다. 형제 가지를 탐색하기 전에 먼저 더 깊이 들어갑니다.

작은 그래프에서 보는 DFS 예시

그래프의 연결이 다음과 같다고 해 봅시다.

• $A$는 $B$와 $C$에 연결됨
• $B$는 $D$와 $E$에 연결됨
• $C$는 $F$에 연결됨

이웃은 항상 왼쪽에서 오른쪽 순서로 확인하고, 시작점은 $A$라고 가정하겠습니다.

DFS는 다음과 같이 진행됩니다.

1. $A$ 방문
2. $B$로 이동
3. $D$로 이동
4. $D$에는 방문하지 않은 이웃이 없으므로 $B$로 되돌아감
5. $B$에서 $E$로 이동
6. $E$ 탐색이 끝났으므로 $B$로 되돌아가고, 다시 $A$로 되돌아감
7. $A$에서 $C$로 이동
8. $C$에서 $F$로 이동

따라서 가능한 DFS 방문 순서 중 하나는 다음과 같습니다.

$$A, B, D, E, C, F$$

핵심은 DFS가 $A \to B$ 쪽을 끝낸 뒤에야 $A \to C$ 쪽을 시작한다는 점입니다. 이웃 순서를 바꾸면 방문 순서도 달라질 수 있습니다.

백트래킹에 스택이 쓰이는 이유

DFS는 막다른 곳에 도달했을 때 어디로 돌아가야 하는지를 항상 기억해야 합니다. 그래서 DFS에서는 스택이 자연스럽게 등장합니다.

재귀 DFS에서는 각 함수 호출이 탐색이 더 깊이 진행되는 동안 대기하고, 되돌아갈 때는 역순으로 복귀합니다. 반복 DFS에서는 노드를 스택에 넣고, 가장 최근의 미완료 지점부터 다시 이어서 탐색할 때 꺼냅니다.

DFS의 시간 복잡도와 공간 복잡도

그래프가 인접 리스트로 저장되어 있고 각 정점을 처음 방문할 때 표시한다면, DFS의 실행 시간은 도달 가능한 그래프 부분에 대해

$$O(V + E)$$

입니다. 여기서 $V$는 정점의 수이고, $E$는 간선의 수입니다.

추가 공간은 보통

$$O(V)$$

입니다. 방문 여부를 저장하는 구조와 재귀 스택 또는 명시적 스택이 모두 정점 수에 비례해 커질 수 있기 때문입니다.

DFS에서 자주 하는 실수

방문한 노드를 표시하지 않는 경우

일반 그래프에서 방문 여부 확인을 빼먹으면, DFS가 사이클을 따라 무한히 반복될 수 있습니다. 트리를 무방향 그래프로 저장한 경우에도, 코드에서 그 상황을 따로 처리하지 않는다면 부모 노드로 바로 되돌아가는 일을 막아야 합니다.

DFS가 최단 경로를 찾는다고 가정하는 경우

DFS는 어떤 경로를 찾을 수는 있지만, 가중치가 없는 그래프에서 일반적으로 최단 경로를 보장하지는 않습니다. 최단 경로가 목표이고 모든 간선의 가중치가 같다면, 보통 BFS가 더 적절한 출발점입니다.

DFS 순서가 유일하다고 생각하는 경우

방문 순서는 이웃 순서에 따라 달라집니다. 그 순서가 바뀌면 탐색 순서도 바뀔 수 있습니다.

깊이 우선 탐색은 언제 쓰일까

DFS는 가장 가까운 거리부터 보는 것보다, 구조를 깊게 탐색하고 싶을 때 유용합니다. 대표적인 활용은 다음과 같습니다.

• 어떤 노드에 도달 가능한지 확인하기
• 연결 요소 찾기
• 일부 그래프 상황에서 사이클 감지하기
• 트리 순회하기
• 미로 탐색이나 퍼즐 탐색처럼 백트래킹 형태의 문제 풀기

DFS가 자주 등장하는 가장 큰 이유는 "깊게 들어가고, 막히면 되돌아온다"라는 방식이 많은 재귀적 문제 구조와 잘 맞기 때문입니다.

DFS와 BFS: 실전에서의 차이

DFS는 먼저 한 갈래를 끝까지 내려갑니다. BFS는 같은 거리의 모든 노드를 먼저 탐색한 뒤 다음 거리로 넘어갑니다.

구조를 깊게 탐색하거나 재귀적 구조가 중요하다면 DFS가 자연스러운 선택인 경우가 많습니다. 반대로 가중치가 없는 그래프에서 최단 경로가 중요하다면, BFS가 더 안전한 첫 선택인 경우가 많습니다.

비슷한 탐색을 직접 해 보기

노드가 6개인 작은 그래프를 그리고, 이웃을 확인하는 고정된 순서를 정해 보세요. 손으로 DFS를 수행하면서 언제 앞으로 나아가고 언제 되돌아오는지 정확히 적어 보세요. 이웃 순서를 바꿨더니 방문 순서가 달라졌다면, 그것은 버그가 아닙니다. 원래 DFS가 그렇게 동작합니다.