한 갈래를 끝까지 가 보고 막히면 되돌아온다

절차적으로 만든 던전에 방이 스무 개 있습니다. 통로를 무작위로 뚫었으니 시작 방에서 모든 방에 갈 수 있는지 확인해야 합니다. 못 가는 방이 하나라도 있으면 그 던전은 클리어가 불가능합니다.

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

한 갈래를 끝까지 간다

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

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

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

재귀와 스택은 같은 코드다

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

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

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

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 로 번호를 만들어 배열로 되돌릴 수 있습니다.

던전이 하나로 이어져 있나

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

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)입니다. 이웃을 적힌 순서가 아니라 무작위 순서로 고르고, 지나갈 때 두 칸 사이의 벽을 부수면 됩니다.

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);
    }
}

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

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

정리

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

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

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

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