---
title: "한 갈래를 끝까지 가 보고 막히면 되돌아온다"
description: "깊이 우선 탐색이 실제로 어떻게 도는지 봅니다. 재귀와 스택이 왜 같은 코드인지, 방문 표시를 어디서 찍어야 하는지, 그리고 던전 연결 검사와 미로 생성에서 이 순서가 왜 필요한지."
author: "유니얼"
pubDate: 2026-09-15
updatedDate: 2026-09-18
category: "programming/algorithm/graph"
tags: ["탐색"]
canonical: https://blog.unialgames.com/posts/algo-dfs/
---
절차적으로 만든 던전에 방이 스무 개 있습니다. 통로를 무작위로 뚫었으니 시작 방에서 모든 방에 갈 수 있는지 확인해야 합니다.
못 가는 방이 하나라도 있으면 그 던전은 클리어가 불가능합니다.

확인하는 방법 하나는 이렇습니다. 시작 방에서 통로 하나를 골라 갈 수 있는 데까지 갑니다.
막히면 갈림길로 되돌아와 안 가 본 통로를 고릅니다. 이걸 되돌아올 곳이 없을 때까지 반복합니다.
**한 갈래를 끝까지 파고들고 막히면 되돌아오는 것**, 이것이 **깊이 우선 탐색(DFS, depth-first search)** 입니다.

## 한 갈래를 끝까지 간다

절차는 셋뿐입니다. 갈 곳을 담아 둘 자리를 만들고, 거기서 하나를 꺼내 방문하고, 그 정점의 이웃을 다시 담습니다.
담아 두는 자리가 **스택**이면 마지막에 넣은 것이 먼저 나옵니다. 그래서 방금 발견한 이웃으로 계속 파고들게 됩니다.

<x-traverse>
<script type="application/json">
{
  "label": "직접 굴려보기",
  "nodes": [
    { "id": "A", "x": 0, "y": 90 },
    { "id": "B", "x": 110, "y": 20 },
    { "id": "C", "x": 110, "y": 160 },
    { "id": "D", "x": 230, "y": 20 },
    { "id": "E", "x": 230, "y": 160 },
    { "id": "F", "x": 350, "y": 90 }
  ],
  "edges": [["A", "B"], ["A", "C"], ["B", "D"], ["C", "E"], ["D", "E"], ["E", "F"]],
  "start": "A",
  "modes": ["dfs"],
  "note": "정점 옆의 숫자가 방문한 순서입니다"
}
</script>
</x-traverse>

A 에서 출발해 B 로 갔다가 D, E 를 지나 F 까지 내려간 뒤에야 C 로 돌아옵니다.
C 는 A 의 바로 옆인데 마지막에 방문합니다. **가까운 순서가 아니라 파고든 순서**입니다.

중간에 이미 가 본 정점이 다시 꺼내지는 장면이 나옵니다. 여러 이웃이 같은 정점을 가리켰기 때문입니다.
그때는 버리고 다음을 꺼냅니다. 이 확인을 빼면 사이클이 있는 그래프에서 영원히 돌게 됩니다.

## 재귀와 스택은 같은 코드다

깊이 우선 탐색은 두 가지 모양으로 씁니다. 하는 일은 같습니다.

<x-compare>
<script type="application/json">
{
  "tabs": [
    {
      "label": "재귀",
      "code": "void Dfs(int cur) {\n    visited[cur] = true;\n    Visit(cur);\n\n    foreach (int next in adj[cur]) {\n        if (visited[next]) continue;\n        Dfs(next);\n    }\n}\n\nDfs(start);",
      "stats": [["갈 곳을 담는 자리", "호출 스택"], ["줄 수", "짧다"], ["깊이 한계", "스택 오버플로"]],
      "tone": "good"
    },
    {
      "label": "직접 만든 스택",
      "code": "var stack = new Stack<int>();\nstack.Push(start);\n\nwhile (stack.Count > 0) {\n    int cur = stack.Pop();\n    if (visited[cur]) continue;\n    visited[cur] = true;\n    Visit(cur);\n\n    foreach (int next in adj[cur]) {\n        if (visited[next]) continue;\n        stack.Push(next);\n    }\n}",
      "stats": [["갈 곳을 담는 자리", "직접 만든 스택"], ["줄 수", "길다"], ["깊이 한계", "힙이 버티는 만큼"]]
    }
  ]
}
</script>
</x-compare>

**재귀판에도 스택은 있습니다.** 눈에 안 보일 뿐 호출 스택이 그 역할을 합니다.
`Dfs(next)` 를 부르면 지금 어디까지 훑었는지가 스택 프레임에 얹히고, 함수가 끝나면 그 자리로 돌아옵니다.
되돌아오기가 공짜로 되는 이유가 이것입니다.

두 코드에서 순서가 한 군데 어긋납니다. 재귀판은 이웃 목록에 적힌 순서대로 들어가는데,
스택판은 **마지막에 넣은 것부터 꺼내므로 이웃을 거꾸로 훑습니다.**
순서를 맞춰야 한다면 이웃을 거꾸로 넣으면 됩니다.

```csharp
for (int i = adj[cur].Count - 1; i >= 0; i--) {
    int next = adj[cur][i];
    if (visited[next]) continue;
    stack.Push(next);
}
```

순서가 결과를 바꾸는 경우가 아니면 신경 쓰지 않아도 됩니다. 연결 여부만 볼 때는 어느 쪽이든 답이 같습니다.

## 깊이가 얼마나 깊어질 수 있나

재귀판의 위험은 하나입니다. **정점이 늘어나는 만큼 호출이 깊어질 수 있습니다.**

일자로 늘어선 그래프를 생각하면 됩니다. 정점 1만 개가 한 줄로 이어져 있으면 재귀는 1만 번 중첩됩니다.
100 곱하기 100 짜리 격자를 훑는 코드도 최악에는 만 단계까지 내려갑니다.
스택 프레임 하나가 수십 바이트만 잡아도 수만 단계가 쌓이면 스택이 터집니다.
게임에서는 보통 스택 오버플로가 곧 프로세스 종료입니다. `try` 로 잡을 수 있는 예외가 아닙니다.

| 무엇을 훑나 | 어느 쪽 |
| --- | --- |
| 방 스무 개짜리 던전, 스킬 트리 | 재귀. 짧고 읽기 쉽습니다 |
| 큰 격자, 정점 수를 예측 못 하는 그래프 | 직접 만든 스택 |
| 방문 순서를 정확히 통제해야 한다 | 직접 만든 스택 |

직접 만든 스택은 힙에 올라가므로 깊이 제한이 사실상 사라집니다. 대신 코드가 길어지고,
되돌아온 뒤에 할 일이 있는 경우 그 상태를 직접 들고 있어야 합니다.

## 방문 표시를 어디서 찍는가

깊이 우선 탐색에서 틀리는 자리는 대부분 여기입니다. 표시를 언제 찍느냐에 따라 결과와 비용이 달라집니다.

- **아예 안 찍으면** 사이클에서 무한히 돕니다. A 에서 B 로 갔다가 B 의 이웃인 A 로 다시 갑니다
- **꺼낼 때 찍으면** 결과는 맞습니다. 대신 같은 정점이 스택에 여러 번 들어갑니다. 이웃 여럿이 같은 정점을 가리키면 그 수만큼 쌓입니다
- **넣을 때 찍으면** 스택에 중복이 안 쌓여 메모리를 아낍니다. 대신 그래프에 따라 방문 순서가 재귀판과 달라질 수 있습니다

위의 애니메이션은 꺼낼 때 찍는 쪽입니다. 이미 가 본 정점이 다시 꺼내졌다가 버려지는 장면이 그래서 나옵니다.
어느 쪽을 고르든 **표시를 찍는 자리는 한 곳**이어야 합니다. 두 곳에 흩어 두면 어디서 빠졌는지 찾기 어려워집니다.

`visited` 를 `HashSet<int>` 로 둘지 `bool[]` 로 둘지도 같이 정합니다.
정점이 0부터 이어진 번호면 배열이 낫습니다. 조회가 배열 인덱스 하나이고, 메모리도 한 덩어리입니다.
좌표나 문자열이 키라면 집합을 쓰되, 격자라면 `y * Width + x` 로 번호를 만들어 배열로 되돌릴 수 있습니다.

## 던전이 하나로 이어져 있나

처음의 문제로 돌아오면 코드는 이렇게 됩니다.

```csharp
int CountIslands(List<int>[] adj) {
    var visited = new bool[adj.Length];
    int islands = 0;

    for (int i = 0; i < adj.Length; i++) {
        if (visited[i]) continue;
        islands++;
        Dfs(i, adj, visited);
    }

    return islands;
}
```

**한 번의 깊이 우선 탐색은 하나의 덩어리를 통째로 칠합니다.** 그래서 탐색을 시작한 횟수가 곧 덩어리의 개수입니다.
1 이면 전부 이어진 던전이고, 2 이상이면 어딘가에 고립된 방이 있습니다.
통로를 더 뚫어야 할지, 그 방을 지워야 할지는 그다음 문제입니다.

방 스무 개에 통로가 서른 개쯤이면 이 검사는 순식간에 끝납니다. 정점과 간선을 한 번씩만 보기 때문입니다.
던전을 만들 때마다 돌려도 부담이 없습니다.

## 막히면 되돌아오는 성질이 곧 미로가 된다

깊이 우선 탐색을 살짝 비틀면 미로 생성기가 됩니다. 이 방식에 붙은 이름이 재귀적 백트래킹(recursive backtracking)입니다. 이웃을 적힌 순서가 아니라 **무작위 순서로** 고르고,
지나갈 때 두 칸 사이의 벽을 부수면 됩니다.

```csharp
void Carve(int x, int y) {
    visited[x, y] = true;

    foreach (var (nx, ny) in Neighbors(x, y).Shuffle()) {
        if (visited[nx, ny]) continue;
        RemoveWall(x, y, nx, ny);
        Carve(nx, ny);
    }
}
```

결과가 재미있습니다. 이 방식으로 만든 미로는 **어느 두 칸 사이에도 길이 정확히 하나뿐**입니다.
이미 방문한 칸으로는 벽을 안 부수니 순환이 생기지 않고, 되돌아오기 덕분에 빠지는 칸도 없기 때문입니다.
그래서 길이 길고 구불구불한, 갈림길이 적은 미로가 나옵니다.

순환이 있는 미로를 원하면 다 만든 뒤에 벽 몇 개를 무작위로 더 부수면 됩니다.
막다른 길이 너무 많다고 느껴질 때 쓰는 손질입니다.

## 정리

깊이 우선 탐색은 갈 곳을 스택에 담아 두고 **마지막에 발견한 곳부터** 파고드는 방식입니다.
가까운 정점이 늦게 방문될 수 있으므로 최단 거리를 구하는 데는 맞지 않습니다.
대신 **어디까지 이어져 있는가**를 묻는 문제에 잘 맞습니다. 연결 검사, 덩어리 세기, 미로 생성이 그렇습니다.

쓸 때 정해야 하는 것은 둘입니다.

- **재귀냐 직접 만든 스택이냐.** 정점 수가 예측 가능하고 적으면 재귀가 짧고 명확합니다. 큰 격자에서는 호출 깊이가 그대로 위험이 됩니다
- **방문 표시를 어디서 찍느냐.** 안 찍으면 무한 루프, 꺼낼 때 찍으면 스택에 중복이 쌓입니다. 한 곳에서만 찍습니다

정점과 간선을 한 번씩 보는 것이 전부라, 비용은 정점 수와 간선 수의 합에 비례합니다.
던전을 만들 때마다 돌려도 되는 수준입니다.