스택과 깊이 우선 탐색 DFS

미로에서 한 길을 따라가고 막히면 다른 길로 돌아오는 탐색은 어떻게 기억할까요? 목표는 스택의 LIFO 약속과 방문 집합이 하는 일을 직접 추적하는 것입니다. 그래프 인접 목록을 먼저 읽으세요.

개념과 약속

스택은 push로 위에 넣고 pop으로 가장 최근 항목을 꺼내는 구조입니다. Python 리스트의 append·끝 pop()으로 구현할 수 있습니다. DFS는 한 방향으로 깊게 진행하다 다른 후보를 처리합니다. 아래 코드는 이웃 목록의 앞 항목이 먼저 나오도록 역순으로 스택에 넣습니다. 탐색 순서는 이웃 순서에 따라 바뀌지만 방문 가능한 집합은 같습니다.

방문 표시를 꺼낼 때 하므로 같은 정점 후보가 스택에 여러 번 들어갈 수 있습니다. 이미 방문했다면 이웃을 다시 넣지 않습니다. 사이클이 있는 미로에서 무한히 도는 일을 막습니다. 단순한 벽 따라가기에는 미로 형태에 관한 조건이 필요하므로 일반 연결 구조에서는 방문 집합을 둔 DFS·BFS로 접근합니다. DFS의 첫 발견 경로가 최단이라는 보장은 없습니다.

손으로 상태 추적하기

시작 A, 이웃 순서 A:[B,C], B:[A,D], C:[A,D], D:[B,C]입니다. 오른쪽이 스택 위입니다.

남은 A,D,C는 이미 방문한 정점이므로 버립니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

def dfs(graph, start):
    if start not in graph:
        raise ValueError("start must be a vertex")
    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.get(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']

왜 맞고 언제 끝나는가

방문한 정점은 시작에서 간선을 따라 도달한 후보뿐입니다. 방문 가능한 정점의 모든 이웃을 스택에 넣으므로 처리할 경로가 누락되지 않습니다. 각 정점의 이웃은 처음 방문할 때 한 번만 넣습니다. 중복 후보는 빠르게 건너뛰어 유한한 간선 수에 비례한 후보 처리를 마칩니다.

비용과 적용 범위

인접 목록으로 시간 O(V+E)입니다. 방문 집합·순서는 O(V)이지만 이처럼 꺼낼 때 방문을 표시하는 구현의 스택에는 O(E) 후보가 동시에 있을 수 있어 추가 공간 O(V+E)로 설명합니다. 발견할 때 표시하거나 재귀 프레임을 모사하는 다른 구현과 공간 설명을 섞지 않습니다. 리스트 끝 꺼내기는 O(1)입니다.

스스로 풀어 보기

1. A의 이웃 순서를 [C,B]로 바꾸면 방문 순서는 어떻게 바뀌나요?
2. 이미 방문한 정점의 이웃도 계속 넣으면 A—B 두 정점에서 종료가 보장될까요?

힌트

1. C를 먼저 따라가고 D를 만납니다.
2. A가 B를 넣고 B가 A를 다시 넣습니다.

해설

1. 이 예에서는 A,C,D,B입니다. E는 여전히 도달하지 못합니다.
2. 보장되지 않습니다. 방문 집합을 검사하는 부분이 정확한 종료 구조의 일부입니다.

흔한 오해

DFS는 가장 짧은 길을 찾기 위한 기본 보장이 없습니다. 방문 순서와 정점까지의 거리도 같은 결과가 아닙니다.

복습과 다음 연결

다음 BFS는 먼저 넣은 후보부터 처리해 거리 층을 만듭니다. 연결이 끊기는 정점 분석은 이중 연결에서 확장합니다.