Algorithm Guidecomplexity: O(V+E)

깊이 우선 탐색 (DFS)

Stack(LIFO)을 사용해 한 경로를 최대한 깊게 파고든 뒤 막히면 되돌아오는(backtrack) 그래프 탐색 알고리즘입니다. 메모리 사용량이 적고(O(h)) 사이클 탐지·위상 정렬·백트래킹 기반 문제 해결의 핵심이 됩니다.

01깊이 우선 탐색 (DFS)

알고리즘 작동 원리 탐색

DFS 시작. 스택(LIFO)으로 한 경로를 최대한 깊게 파고든 뒤, 막히면 되돌아와 다음 경로를 탐색합니다. 목표는 H.

A를 pop해 확장합니다. 이웃 B, C를 스택에 push — 나중에 넣은 C가 다음에 먼저 나옵니다.

C를 pop합니다. C ≠ H 이므로 이웃 F, G를 스택에 push. 오른쪽 서브트리로 깊게 내려갑니다.

G를 pop합니다. 리프 노드라 추가할 이웃이 없어 되돌아가야 합니다. 스택에서 다음 노드를 꺼냅니다.

F를 pop합니다. F ≠ H 이므로 이웃 H를 push합니다(C는 이미 방문했으므로 건너뜁니다).

H를 pop합니다. 목표와 일치 — DFS 경로 A → C → F → H (깊이 3)로 도달했습니다.

탐색 완료 · 경로 A → C → F → H (비용 3). 메모리 O(h)로 가볍고, 사이클 탐지·백트래킹의 기반입니다.

Live Python

1def dfs(graph, start, target):

# stack = [A]

2 stack = [start]

3 visited = set()

4 parent = {start: None}

5 while stack:

6 current = stack.pop()

7 if current in visited:

8 continue

9 if current == target:

10 return reconstruct(parent, target)

11 visited.add(current)

12 for nb in graph[current]:

13 if nb not in visited:

14 parent[nb] = current

15 stack.append(nb)

16 return None

1 / 7

02 쉽게 이해하기

For Everyone

🔑핵심 동작

한 갈래를 갈 수 있는 데까지 따라가고, 막히면 마지막 분기점으로 되돌아옵니다.

💡쉽게 말하면

스택으로 한 경로를 최대한 깊게 탐색하고, 막히면 되돌아갑니다(backtrack).

메모리가 적게 들어요.

📍어디에 쓰나

–사이클 탐지
–위상 정렬
–백트래킹 문제

03 파이썬 구현 코드

깊이 우선 탐색 (DFS)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def dfs(graph, start, target):
    stack = [start]
    visited = set()
    parent = {start: None}
    while stack:
        current = stack.pop()
        if current in visited:
            continue
        if current == target:
            return reconstruct(parent, target)
        visited.add(current)
        for nb in graph[current]:
            if nb not in visited:
                parent[nb] = current
                stack.append(nb)
    return None