스택과 깊이 우선 탐색 DFS

미로를 빠져나가는 한 가지 방법은 갈림길에서 아무 길이나 골라 막다른 곳이 나올 때까지 따라가고, 막히면 가장 최근에 지난 갈림길로 돌아가 아직 가 보지 않은 길을 고르는 것입니다. 이 방법에서는 "가장 최근의 갈림길"을 기억하는 것이 중요합니다. 마지막에 기억한 것을 가장 먼저 꺼내 쓰는 구조, 곧 스택이 바로 이 일에 맞습니다. 그래프에서 이렇게 한 방향으로 깊이 들어갔다가 되돌아오며 탐색하는 방법을 깊이 우선 탐색(depth-first search, DFS)이라고 합니다. 이 글에서는 스택으로 DFS를 만들고, DFS가 무엇을 보장하고 무엇을 보장하지 않는지 살펴봅니다.

스택과 큐: 꺼내는 순서가 다르다

스택(stack)은 마지막에 넣은 것을 가장 먼저 꺼내는 구조이고, 이 성질을 LIFO(last in, first out)라고 합니다. 반대로 먼저 넣은 것을 먼저 꺼내는 구조는 큐(queue)라 하고, 이 성질을 FIFO(first in, first out)라고 합니다. 같은 값을 같은 순서로 넣어도 두 구조는 다른 값을 먼저 내놓습니다.

A, B, C를 차례로 넣었을 때 스택은 C를, 큐는 A를 먼저 꺼냅니다. 그래프 탐색에서는 앞으로 방문할 정점 후보를 이런 구조에 넣어 두고 하나씩 꺼내 처리하므로, 어느 구조를 쓰느냐가 곧 탐색의 순서를 정합니다. 스택을 쓰면 가장 최근에 발견한 후보부터 처리하므로 깊이 들어가는 DFS가 되고, 큐를 쓰면 먼저 발견한 후보부터 처리하므로 다음 글의 너비 우선 탐색이 됩니다.

Python에서는 리스트가 그대로 스택이 됩니다. append로 끝에 넣고 인자 없는 pop()으로 끝에서 꺼내면, 둘 다 리스트·배열·문자열·딕셔너리의 역할에서 본 것처럼 O(1)입니다.

스택으로 만든 DFS

DFS는 시작 정점 하나를 스택에 넣고 시작합니다. 스택에서 정점을 하나 꺼내 처음 보는 정점이면 방문했다고 표시하고, 그 이웃들을 스택에 넣습니다. 이미 방문한 정점이면 아무것도 하지 않고 다음 정점을 꺼냅니다. 스택이 빌 때까지 이 일을 되풀이합니다.

방문 표시가 없으면 어떻게 될까요? 무방향 그래프에서 A의 이웃에는 B가, B의 이웃에는 A가 있으므로 A가 B를 넣고 B가 다시 A를 넣는 일이 끝없이 되풀이됩니다. 방문한 정점의 집합 visited는 같은 정점을 두 번 처리하지 않게 해서 이런 무한 반복을 막습니다.

def dfs(graph, start):
    visited, order, stack = set(), [], [start]
    while stack:
        vertex = stack.pop()
        if vertex in visited:
            continue
        visited.add(vertex)
        order.append(vertex)
        stack.extend(reversed(graph[vertex]))
    return order


graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C"], "E": []}
print(dfs(graph, "A"))
print(dfs(graph, "E"))

['A', 'B', 'D', 'C']
['E']

continue는 반복문의 나머지를 건너뛰고 다음 반복으로 넘어가는 문장입니다. 이웃을 reversed로 거꾸로 넣는 것은, 스택이 마지막에 넣은 것을 먼저 꺼내기 때문에 이웃 목록의 첫 이웃이 먼저 처리되도록 하려는 것입니다. E는 이웃이 없는 고립점이라 E에서 시작하면 E만 방문하고, A에서 시작해도 E에는 닿지 않습니다.

A에서 시작하는 과정을 따라가 보겠습니다. 스택은 오른쪽 끝이 위, 곧 다음에 꺼낼 쪽입니다.

마지막 줄 뒤에 스택에 남은 A, D, C는 모두 이미 방문한 정점이라 차례로 건너뛰고 탐색이 끝납니다. B를 방문한 뒤 C보다 D를 먼저 방문한 것이 DFS의 특징입니다. A의 이웃인 C가 먼저 발견되었지만, 더 최근에 발견된 B의 이웃 D를 먼저 따라가 깊이 들어간 것입니다.

재귀로 쓴 DFS

DFS는 재귀로도 자연스럽게 쓸 수 있습니다. 한 정점을 방문하고, 그 이웃 가운데 방문하지 않은 정점마다 같은 함수를 부르면 됩니다. 이때는 우리가 스택을 직접 관리하지 않아도 호출 스택이 "돌아갈 곳"을 기억해 줍니다. 이웃 하나를 끝까지 탐색한 호출이 돌아오면, 반복문이 그다음 이웃으로 넘어가는 것이 미로에서 갈림길로 돌아오는 일에 해당합니다.

def dfs_recursive(graph, vertex, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(vertex)
    order.append(vertex)
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, order)
    return order


graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C"], "E": []}
print(dfs_recursive(graph, "A"))

['A', 'B', 'D', 'C']

visited=None처럼 기본값을 None으로 두고 함수 안에서 새 집합을 만드는 것은, 기본값에 set()을 바로 쓰면 함수를 부를 때마다 같은 집합을 계속 함께 쓰게 되기 때문입니다. 방문 순서는 스택으로 만든 DFS와 같습니다. 재귀로 쓴 DFS는 짧고 읽기 쉽지만, 한 길이 아주 길면 Python의 재귀 깊이 한도에 걸립니다. 예를 들어 정점 2001개가 한 줄로 이어진 그래프에서는 RecursionError가 나지만, 스택으로 만든 DFS는 문제없이 2001개를 모두 방문합니다. 그래서 큰 그래프에서는 직접 스택을 쓰는 편이 안전합니다.

DFS로 할 수 있는 일

DFS는 시작 정점에서 간선을 따라 닿을 수 있는 정점을 모두 찾습니다. 이 성질을 이용하면 그래프가 몇 덩어리로 나뉘어 있는지도 셀 수 있습니다. 서로 이어진 정점들의 덩어리를 연결 성분(connected component)이라고 하는데, 아직 방문하지 않은 정점에서 DFS를 시작할 때마다 새 연결 성분을 하나 찾은 것입니다.

def count_components(graph):
    seen = set()
    count = 0
    for start in graph:
        if start in seen:
            continue
        count += 1
        stack = [start]
        while stack:
            vertex = stack.pop()
            if vertex not in seen:
                seen.add(vertex)
                stack.extend(graph[vertex])
    return count


graph = {"A": ["B"], "B": ["A", "C"], "C": ["B"], "D": [], "E": ["F"], "F": ["E"]}
print(count_components(graph))

3

A에서 시작한 DFS가 A, B, C를 방문하고, 다음으로 방문하지 않은 D에서 D 하나를, E에서 E와 F를 방문해 연결 성분이 3개입니다. 같은 방법으로 미로의 두 칸이 이어져 있는지, 네트워크가 끊어진 곳이 있는지를 확인할 수 있습니다. 앞 글의 오일러 판정에서 간선이 있는 정점들이 모두 이어져 있는지 확인한 것도 이 방법이었습니다.

왜 모두 찾고 왜 끝나는가

DFS가 방문하는 정점은 모두 시작 정점에서 닿을 수 있는 정점입니다. 스택에는 시작 정점과, 이미 방문한 정점의 이웃만 들어가기 때문입니다. 거꾸로 닿을 수 있는 정점은 모두 방문합니다. 시작 정점에서 어떤 정점 v까지 이어진 길이 있다고 하면, 그 길의 정점들은 차례로 방문됩니다. 길 위의 한 정점이 방문되면 그 이웃인 다음 정점이 스택에 들어가고, 스택이 빌 때까지 꺼내므로 언젠가 꺼내져 방문되기 때문입니다.

끝나는 이유는 방문 표시에 있습니다. 각 정점은 많아야 한 번 방문되고, 이웃을 스택에 넣는 일은 방문할 때만 하므로 정점마다 한 번뿐입니다. 그래서 스택에 들어가는 항목은 시작 정점 하나와 방문한 정점들의 이웃을 모두 합한 만큼, 무방향 그래프라면 많아야 1 + 2E개입니다. 넣는 항목이 유한하므로 꺼내는 일도 언젠가 끝납니다.

비용

각 정점을 한 번 방문하고 각 정점의 이웃 목록을 한 번 훑으므로, 인접 목록으로 표현한 그래프에서 DFS의 시간은 O(V + E)입니다. 방문 집합과 방문 순서는 O(V)의 공간을 씁니다. 이 글의 구현은 꺼낼 때 방문을 표시하므로, 같은 정점이 아직 꺼내지 않은 채로 스택에 여러 번 들어 있을 수 있습니다. 앞의 추적에서 C가 스택에 두 번 들어 있었던 것이 그 예이고, 스택에는 많아야 O(E)개의 항목이 쌓입니다. 넣을 때 방문을 표시하면 스택을 O(V)로 줄일 수 있지만, 그러면 정점을 처리하는 순서가 재귀로 쓴 DFS와 달라질 수 있습니다.

DFS는 최단 경로를 찾지 않는다

DFS로 각 정점에 처음 도착할 때 어느 정점에서 왔는지 기록해 두면, 시작 정점에서 그 정점까지 가는 길을 되짚을 수 있습니다. 하지만 이렇게 얻은 길이 가장 짧은 길이라는 보장은 없습니다. 아래 코드는 스택에 (정점, 온 곳) 쌍을 넣어 처음 방문할 때의 온 곳을 parent에 기록하고, C까지의 길을 되짚습니다.

def dfs_parents(graph, start):
    parent, stack = {}, [(start, None)]
    while stack:
        vertex, came_from = stack.pop()
        if vertex in parent:
            continue
        parent[vertex] = came_from
        for neighbor in reversed(graph[vertex]):
            stack.append((neighbor, vertex))
    return parent


def path_to(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]


graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C"], "E": []}
parent = dfs_parents(graph, "A")
print(parent)
print(path_to(parent, "C"))

{'A': None, 'B': 'A', 'D': 'B', 'C': 'D'}
['A', 'B', 'D', 'C']

path_to는 목표 정점에서 parent를 따라 시작 정점까지 거슬러 올라간 뒤, [::-1]로 순서를 뒤집어 돌려줍니다. A와 C는 간선 하나로 바로 이어져 있는데도, DFS는 B와 D를 거치는 간선 세 개짜리 길을 찾았습니다. B 쪽으로 깊이 들어가다가 D에서 C를 먼저 만났기 때문입니다. DFS는 닿을 수 있는지를 알려 줄 뿐 가장 가까운 길을 알려 주지는 않습니다. 가장 적은 간선으로 가는 길이 필요하면 다음 글의 너비 우선 탐색을 씁니다.

정리

• 스택은 마지막에 넣은 것을 먼저 꺼내는 LIFO 구조이고, Python 리스트의 append와 pop()으로 O(1)에 쓸 수 있습니다.
• DFS는 스택에서 정점을 꺼내 처음 보는 정점이면 방문하고 그 이웃을 넣는 일을 되풀이하며, 가장 최근에 발견한 길을 먼저 깊이 따라갑니다.
• 방문 집합이 같은 정점을 다시 처리하지 않게 해서 사이클이 있는 그래프에서도 탐색이 끝나게 합니다.
• 재귀로 쓴 DFS는 호출 스택이 돌아갈 곳을 기억해 짧게 쓸 수 있지만, 깊은 그래프에서는 재귀 깊이 한도에 걸립니다.
• DFS는 시작 정점에서 닿을 수 있는 정점을 O(V + E)에 모두 찾으며, 연결 성분을 세는 데 쓸 수 있습니다. 하지만 찾은 길이 가장 짧다는 보장은 없습니다.

연습 문제

1. 이웃 순서를 바꾸면

본문 그래프에서 A의 이웃 순서를 ["C", "B"]로 바꾸면 A에서 시작한 DFS의 방문 순서는 어떻게 될까요? 방문하는 정점의 집합은 달라지나요?

2. 방문 표시 없이 탐색하면

정점 A와 B가 간선 하나로 이어진 그래프 {"A": ["B"], "B": ["A"]}에서, visited 확인을 빼고 꺼낸 정점의 이웃을 무조건 스택에 넣으면 어떻게 될까요?

3. 방향 그래프에서 닿는 정점

방향 그래프 {"A": ["B"], "B": ["C"], "C": ["A"], "D": ["C"]}에서 A에서 시작한 DFS와 D에서 시작한 DFS는 각각 어떤 정점들을 방문할까요?

다음 글 큐와 너비 우선 탐색 BFS에서는 스택 대신 큐를 써서 가까운 정점부터 방문하고, 가장 적은 간선으로 가는 길을 찾습니다. 그래프에서 어느 정점이 빠지면 연결이 끊기는지를 DFS로 찾는 방법은 선택 심화: 단절점·low·이중 연결 성분에서 다룹니다.