깊이 우선 탐색: 박혔다가, 되돌아오기

"BFS 가 고르게 바깥으로 퍼지는 물결이면, DFS 는 막다른 길에 부딪힐 때까지 복도 하나를 돌진하다 되돌아 다음을 시도하는 탐험가 하나야. 같은 그래프, 정반대 기질."

알고리즘: 스택 (또는 콜 스택)

깊이 우선 탐색은 BFS 의 큐를 스택으로 바꿔 — 그리고 제일 단순한 스택이 콜 스택이라, DFS 는 자연스레 재귀적이야: 노드 방문, visited 표시, 그다음 각 방문 안 한 이웃으로 재귀. 재귀가 한 경로를 갈 수 있는 만큼 깊이 다이브; 노드에 방문 안 한 이웃이 없으면, 반환 (백트랙) 하고 이전 레벨이 다음 이웃을 시도해. 명시적 스택으로 DFS 를 반복으로도 쓸 수 있어 — 시작 push, 노드 pop, 방문 안 한 이웃 push — 아주 깊은 그래프에서 Python 재귀 한계를 피해.

성격: 넓게 아니라 깊게

DFS 는 대안을 고려하기 전에 한 경로에 강하게 헌신해. 그게 최단 경로엔 틀린 도구로 만들어 — 짧은 게 있었는데 길고 구불구불한 복도로 노드에 닿을 수 있어 — 근데 완전히 탐색해야 하는 문제 가문엔 맞는 도구야:

경로 존재 — "A 에서 B 로 가는 길이 있어?"
순환 검출 — DFS 가 현재 경로의 노드를 재방문하면 순환이야.
위상 정렬 — 의존성으로 작업 순서 매기기 (다음 lesson) 가 DFS 후위를 써.
연결 요소 — 방문 안 한 각 노드에서 DFS 가 요소 하나를 깎아내.
백트래킹 — 미로, 퍼즐, 순열: DFS 가 Recursion 트랙에서 만날 백트래킹 엔진 그 자체야.

DFS 는 스택 (또는 재귀) frontier 를 써: 한 경로로 깊이 박히고, 막다른 길에서 백트랙. 최단 경로를 안 찾지만, 순환 검출, 위상 정렬, 연결 요소, 백트래킹의 엔진이야. visited 집합 여전히 필수.

재귀 vs 반복

재귀 DFS 는 아름답게 짧고 대부분 그래프의 기본이야. 근데 콜 스택이 O(깊이) 공간을 쓰고, 깊거나 퇴화한 그래프가 Python 재귀 한계를 터뜨릴 수 있어 (RecursionError). 아주 깊을 수 있는 그래프엔, 명시적 스택 있는 반복 버전으로 바꿔 — 같은 로직, 콜 스택 대신 네 스택, 네 것 말곤 깊이 한계 없음. 정확히 Stacks 트랙의 스택/재귀 동등성을, 중요한 데 적용한 거야.

피파의 고백

난 알고 보니 5만 노드 사슬인 그래프에 재귀 DFS 를 썼고, 순회 중간에 RecursionError 로 죽었어. 아빠는 알고리즘을 안 바꿨어 — 스택을 바꿨어: 같은 DFS, 근데 콜 스택 대신 명시적 리스트를 frontier 로. 깊이 한계 없음, 같은 결과. Stacks-트랙 교훈을 굳혔어: 재귀는 그냥 네가 선언 안 해도 된 스택이고 — 가끔은 네 걸 선언해야 해.

Code

DFS 재귀와 반복 (같은 frontier, 네 스택)·python

graph = {
    "A": ["B", "C"], "B": ["D", "E"], "C": ["F"],
    "D": [], "E": ["F"], "F": [],
}

# 재귀 DFS — 우아; 콜 스택이 frontier 그 자체.
def dfs_recursive(graph, node, visited=None, order=None):
    if visited is None: visited, order = set(), []
    visited.add(node); order.append(node)
    for nb in graph[node]:
        if nb not in visited:
            dfs_recursive(graph, nb, visited, order)   # 깊이 박혀
    return order

print("recursive:", dfs_recursive(graph, "A"))   # ['A','B','D','E','F','C']

# 반복 DFS — 명시적 스택; 깊은 그래프에서 재귀-한계 위험 없음.
def dfs_iterative(graph, start):
    visited, order, stack = set(), [], [start]
    while stack:
        node = stack.pop()                   # LIFO -> 깊이 우선
        if node in visited: continue
        visited.add(node); order.append(node)
        for nb in reversed(graph[node]):     # 재귀 순서 맞추려 reversed
            if nb not in visited:
                stack.append(nb)
    return order

print("iterative:", dfs_iterative(graph, "A"))   # 같은 깊이-우선 성격

Exercise

그래프 A→B, A→C, B→D, C→D 에, A 에서 DFS 를 돌려 가능한 방문 순서를 써. 그다음 A→C→D 가 같은 길이인데도 DFS 가 D 에 닿으려 A→B→D 경로를 보고할 수 있는 이유를 — 그리고 그게 왜 DFS 를 최단 경로엔 틀린 선택, '어떤 경로든 있어?' 엔 맞는 선택으로 만드는지 설명해.

Hint

DFS 는 A, B, D (B 가지를 먼저 박아) 를 방문해 C 를 시도하기 전에 B 로 D 에 닿을 수 있어. 거리가 아니라 깊이에 헌신해, 그래서 찾은 경로가 최단 보장 안 됨 — 근데 *어떤* 경로든 있으면 DFS 가 하나 찾아, 그게 '도달 가능성' 이 필요한 전부.

알고리즘: 스택 (또는 콜 스택)

성격: 넓게 아니라 깊게

재귀 vs 반복

피파의 고백

Code

External links

Exercise

Progress

댓글 0