[정글 베이직 24] DFS(깊이 우선 탐색)

DFS는 그래프를 깊게 탐색하는 방식입니다. 재귀 함수와 함께 이해하면 훨씬 쉽게 익힐 수 있습니다.

DFS란?

DFS(Depth-First Search)는 현재 갈 수 있는 길이 있다면 한 방향으로 끝까지 내려간 뒤, 더 이상 갈 곳이 없을 때 되돌아오면서 탐색하는 방식입니다.

깊이 우선 탐색

재귀 또는 스택 사용

예제 그래프

0 ─── 1
│       │
└ 2 ── 3

시작 정점

0에서 시작합니다.

DFS의 느낌을 그림처럼 이해하기

예를 들어 인접 리스트 순서가 그대로 유지된다면 다음과 같이 진행될 수 있습니다.

0 → 1 → 2 → 3

물론 DFS는 인접 정점의 저장 순서에 따라 방문 결과가 달라질 수 있습니다. 그래서 문제에 따라 DFS 결과가 여러 개 나올 수도 있습니다.

재귀 호출 흐름

1단계

dfs(0)을 호출하고 0을 방문합니다.

2단계

0의 인접 정점 중 방문하지 않은 1로 내려갑니다.

3단계

1의 인접 정점 중 방문하지 않은 2로 내려갑니다.

4단계

2의 인접 정점 중 방문하지 않은 3으로 내려갑니다. 이후 더 갈 곳이 없으면 다시 되돌아옵니다.

풀이 핵심

현재 정점을 방문하고, 인접한 정점 중 아직 방문하지 않은 정점에 대해 재귀 호출을 수행하면 됩니다. 이때 방문한 정점을 기록하는 visited 리스트가 필수입니다.

정답 코드

def dfs(graph, start, visited=None):
    """
    깊이 우선 탐색 (재귀)
    """
    if visited is None:
        visited = []

    visited.append(start)

    for next_node in graph[start]:
        if next_node not in visited:
            dfs(graph, next_node, visited)

    return visited

# 테스트 케이스
if __name__ == "__main__":
    graph = {
        0: [1, 2],
        1: [0, 2],
        2: [0, 1, 3],
        3: [2]
    }

    print("=== DFS (깊이 우선 탐색) ===")
    result = dfs(graph, 0)
    print(f"시작 정점: 0")
    print(f"방문 순서: {result}")

BFS와 비교하면?

구분	BFS	DFS
탐색 방향	가까운 곳부터	깊게 끝까지
주요 도구	큐	재귀 또는 스택
이미지 느낌	층별 확산	한 갈래 깊게 전진

한 줄 요약

DFS는 방문 → 아직 안 간 이웃으로 재귀 호출의 반복입니다.