깊이 우선 탐색: 끝까지 파고들었다가 되돌아오기

"BFS가 사방으로 고르게 퍼지는 물결이라면, DFS는 막다른 길에 부딪힐 때까지 복도 하나를 내달리다가 돌아 나와 다음을 시도하는 탐험가 한 명이야. 같은 그래프인데 기질이 정반대지."

알고리즘: 스택, 또는 콜 스택

깊이 우선 탐색은 BFS의 큐를 스택으로 바꾼 거야. 그리고 가장 단순한 스택이 콜 스택이니까 DFS는 자연스럽게 재귀가 돼. 노드를 방문하고, 방문 표시를 하고, 아직 안 간 이웃마다 재귀로 들어가는 거지. 재귀가 한 경로를 갈 수 있는 데까지 파고들어. 그러다 어떤 노드에 안 가본 이웃이 없으면 반환하고, 그러니까 되돌아 나오고, 이전 레벨이 다음 이웃을 시도해. 명시적인 스택을 써서 반복으로 짤 수도 있어. 시작 노드를 넣고, 노드를 꺼내고, 안 가본 이웃을 넣는 식이지. 아주 깊은 그래프에서 Python 재귀 한계를 피할 수 있고.

성격: 넓게가 아니라 깊게

DFS는 다른 선택지를 보기 전에 한 경로에 강하게 매달려. 그래서 최단 경로에는 맞지 않는 도구야. 짧은 길이 있었는데도 길고 구불구불한 복도를 돌아 노드에 닿을 수 있거든. 대신 남김없이 탐색해야 하는 문제 무리에는 딱 맞아.

경로 존재 확인 — "A에서 B로 가는 길이 있기는 해?"
순환 검출 — 방향 그래프에서는 지금 재귀 경로 위에 있는 노드를 다시 만나면 사이클이야. 무방향 그래프에서는 방금 타고 온 부모 간선을 빼고 나서 방문한 노드를 만나는지 봐야 하고.
위상 정렬 — 의존성에 따라 작업 순서를 매기는 건데, 바로 다음에 나오고 DFS 후위 순회를 써.
연결 요소 — 아직 안 가본 노드마다 DFS를 돌리면 요소가 하나씩 떨어져 나와.
백트래킹 — 미로, 퍼즐, 순열 같은 것들이야. 재귀 트랙에서 만날 백트래킹 엔진이 바로 DFS거든.

DFS는 스택, 또는 재귀를 경계로 삼아. 한 경로로 깊이 파고들다가 막다른 길에서 되돌아 나오지. 최단 경로는 못 찾지만 순환 검출, 위상 정렬, 연결 요소, 백트래킹을 굴리는 엔진이야. 방문 집합은 여기서도 필수고.

재귀냐 반복이냐

재귀 DFS는 아름답게 짧아서 웬만한 그래프에는 이게 기본이야. 다만 콜 스택이 O(깊이)만큼 공간을 쓰고, 깊거나 한쪽으로 퇴화한 그래프는 Python 재귀 한계를 터뜨릴 수 있어(RecursionError). 아주 깊어질 수 있는 그래프라면 명시적 스택을 쓰는 반복 버전으로 바꿔. 로직은 똑같고 콜 스택 대신 직접 만든 스택을 쓰는 것뿐이야. 깊이 한계도 직접 정하는 것 말고는 없고. 스택과 큐 트랙에서 본 스택과 재귀의 등가성을 중요한 자리에 적용한 거지.

피파의 고백

알고 보니 5만 노드짜리 사슬이었던 그래프에 재귀 DFS를 돌렸다가 순회 도중에 RecursionError로 죽은 적이 있어. 아빠는 알고리즘을 안 바꿨어. 스택을 바꿨지. 똑같은 DFS인데 콜 스택 대신 명시적인 리스트를 경계로 쓴 거야. 깊이 한계도 없고 결과도 같았어. 스택과 큐 트랙에서 배운 게 그때 굳어졌어. 재귀는 그냥 내가 선언하지 않아도 됐던 스택이고, 가끔은 직접 선언해야 한다는 것.

Code

DFS의 재귀 버전과 반복 버전 (같은 경계, 직접 만든 스택)·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는 B 가지부터 파고드니까 C를 시도하기도 전에 A, B, D를 방문하면서 B를 거쳐 D에 닿을 수 있어. 거리가 아니라 깊이에 매달리니까 찾아낸 경로가 최단이라는 보장이 없지. 대신 경로가 하나라도 있으면 DFS는 반드시 하나를 찾아내고, '도달 가능한가'를 묻는 문제에는 그거면 충분해.

알고리즘: 스택, 또는 콜 스택

성격: 넓게가 아니라 깊게

재귀냐 반복이냐

피파의 고백

Code

External links

Exercise

Progress

댓글 0