Algorithm Guidecomplexity: O(V+E)

깊이 우선 탐색 (DFS)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

HOVER OR SCROLL

Depth-First Search

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

Logic Node1 / 7

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

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