기쁘달

DFS (깊이 우선 탐색)

10 min read

개념

Depth-First Search - 깊이 우선 탐색

한 방향으로 끝까지 탐색한 후 되돌아와 다른 방향 탐색

시간복잡도

표현 방법시간복잡도
인접 리스트O(V + E)
인접 행렬O(V²)

V: 정점 수, E: 간선 수

특징

동작 방식

그래프:
    1
   / \
  2   3
 / \
4   5

탐색 순서: 1 → 2 → 4 → 5 → 3
(왼쪽 끝까지 간 후 되돌아옴)

장점

  • 메모리 효율적: 현재 경로만 저장
  • 경로 찾기: 목표까지의 경로 추적 가능
  • 백트래킹: 되돌아가며 탐색

단점

  • 최단 경로 보장 안 됨: 먼저 찾은 경로가 최단 아닐 수 있음
  • 무한 루프 가능: 방문 체크 필수

구현 방법

1. 재귀 (Recursive)

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
 
    # 현재 노드 방문
    visited.add(start)
    print(start, end=' ')
 
    # 인접 노드 방문
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
 
    return visited
 
# 테스트
graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1],
    4: [2],
    5: [2]
}
 
dfs_recursive(graph, 1)  # 1 2 4 5 3
 
# 시간복잡도: O(V + E)
# 공간복잡도: O(V) - 재귀 스택 + visited

2. 스택 (Iterative)

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
 
    while stack:
        vertex = stack.pop()
 
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=' ')
 
            # 인접 노드를 스택에 추가 (역순으로 추가하면 정순 방문)
            for neighbor in reversed(graph[vertex]):
                if neighbor not in visited:
                    stack.append(neighbor)
 
    return visited
 
# 테스트
dfs_iterative(graph, 1)  # 1 2 4 5 3
 
# 시간복잡도: O(V + E)
# 공간복잡도: O(V)

3. 경로 반환

def dfs_path(graph, start, end, path=None):
    if path is None:
        path = []
 
    path = path + [start]
 
    # 목표 도달
    if start == end:
        return path
 
    # 인접 노드 탐색
    for neighbor in graph[start]:
        if neighbor not in path:
            new_path = dfs_path(graph, neighbor, end, path)
            if new_path:
                return new_path
 
    return None
 
# 테스트
print(dfs_path(graph, 1, 5))  # [1, 2, 5]

4. 모든 경로 찾기

def dfs_all_paths(graph, start, end, path=None, paths=None):
    if path is None:
        path = []
    if paths is None:
        paths = []
 
    path = path + [start]
 
    if start == end:
        paths.append(path)
    else:
        for neighbor in graph[start]:
            if neighbor not in path:
                dfs_all_paths(graph, neighbor, end, path, paths)
 
    return paths
 
# 테스트
graph2 = {
    1: [2, 3],
    2: [4],
    3: [4],
    4: []
}
print(dfs_all_paths(graph2, 1, 4))  # [[1, 2, 4], [1, 3, 4]]

자주 나오는 문제 유형

1. 연결 요소 개수

문제: 그래프의 연결 요소(Connected Component) 개수

def count_components(n, edges):
    # 그래프 생성
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
 
    visited = [False] * n
    count = 0
 
    def dfs(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)
 
    # 모든 노드에서 DFS 시도
    for i in range(n):
        if not visited[i]:
            dfs(i)
            count += 1
 
    return count
 
# 테스트
print(count_components(5, [[0,1], [1,2], [3,4]]))  # 2
 
# 시간복잡도: O(V + E)

핵심: 방문하지 않은 노드에서 DFS 시작할 때마다 count++

2. 섬의 개수

문제: 2D 그리드에서 1로 연결된 섬의 개수

def num_islands(grid):
    if not grid:
        return 0
 
    rows, cols = len(grid), len(grid[0])
    count = 0
 
    def dfs(r, c):
        # 범위 체크 및 물 체크
        if (r < 0 or r >= rows or c < 0 or c >= cols or
            grid[r][c] == '0'):
            return
 
        # 방문 표시
        grid[r][c] = '0'
 
        # 4방향 탐색
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)
 
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1
 
    return count
 
# 테스트
grid = [
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"]
]
print(num_islands(grid))  # 3
 
# 시간복잡도: O(rows × cols)

핵심: 땅(1)을 만나면 DFS로 연결된 모든 땅을 0으로 변경

3. 사이클 탐지 (무방향 그래프)

문제: 그래프에 사이클이 있는지 확인

def has_cycle(graph, n):
    visited = [False] * n
 
    def dfs(node, parent):
        visited[node] = True
 
        for neighbor in graph[node]:
            if not visited[neighbor]:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                # 방문했고 부모가 아니면 사이클
                return True
 
        return False
 
    for i in range(n):
        if not visited[i]:
            if dfs(i, -1):
                return True
 
    return False
 
# 테스트
graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1]
}
print(has_cycle(graph, 3))  # True (0-1-2-0)
 
# 시간복잡도: O(V + E)

핵심: 방문한 노드를 다시 만났는데 부모가 아니면 사이클

4. 사이클 탐지 (방향 그래프)

문제: 방향 그래프에서 사이클 탐지

def has_cycle_directed(graph, n):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
 
    def dfs(node):
        if color[node] == GRAY:
            return True  # 사이클 발견
 
        if color[node] == BLACK:
            return False  # 이미 처리됨
 
        color[node] = GRAY  # 방문 중
 
        for neighbor in graph[node]:
            if dfs(neighbor):
                return True
 
        color[node] = BLACK  # 처리 완료
        return False
 
    for i in range(n):
        if color[i] == WHITE:
            if dfs(i):
                return True
 
    return False
 
# 테스트
graph = {
    0: [1],
    1: [2],
    2: [0]
}
print(has_cycle_directed(graph, 3))  # True (0→1→2→0)
 
# 시간복잡도: O(V + E)

핵심: 3색 DFS - WHITE(미방문), GRAY(방문 중), BLACK(완료)

5. 위상 정렬 (Topological Sort)

문제: 방향 비순환 그래프(DAG)의 위상 정렬

def topological_sort(graph, n):
    visited = [False] * n
    stack = []
 
    def dfs(node):
        visited[node] = True
 
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)
 
        stack.append(node)
 
    for i in range(n):
        if not visited[i]:
            dfs(i)
 
    return stack[::-1]  # 역순
 
# 테스트
graph = {
    0: [1, 2],
    1: [3],
    2: [3],
    3: []
}
print(topological_sort(graph, 4))  # [0, 2, 1, 3] 또는 [0, 1, 2, 3]
 
# 시간복잡도: O(V + E)

핵심: DFS 완료 순서의 역순이 위상 정렬

6. 단절점 (Articulation Point)

문제: 그래프에서 제거하면 연결 요소가 증가하는 정점

def find_articulation_points(graph, n):
    visited = [False] * n
    discovery = [0] * n
    low = [0] * n
    parent = [-1] * n
    ap = [False] * n
    timer = [0]
 
    def dfs(u):
        children = 0
        visited[u] = True
        discovery[u] = low[u] = timer[0]
        timer[0] += 1
 
        for v in graph[u]:
            if not visited[v]:
                children += 1
                parent[v] = u
                dfs(v)
 
                low[u] = min(low[u], low[v])
 
                # 루트 노드: 자식이 2개 이상
                if parent[u] == -1 and children > 1:
                    ap[u] = True
 
                # 비루트 노드: low[v] >= discovery[u]
                if parent[u] != -1 and low[v] >= discovery[u]:
                    ap[u] = True
 
            elif v != parent[u]:
                low[u] = min(low[u], discovery[v])
 
    for i in range(n):
        if not visited[i]:
            dfs(i)
 
    return [i for i in range(n) if ap[i]]
 
# 시간복잡도: O(V + E)

핵심: Tarjan 알고리즘 - low, discovery 값 비교

추천 연습 문제

기초

중급

고급

핵심 요약

개념설명
탐색 방식끝까지 탐색 후 되돌아옴
구현재귀 또는 스택
시간복잡도O(V + E)
활용경로 찾기, 사이클 탐지, 위상 정렬

DFS 템플릿

기본 템플릿

def dfs(node, visited):
    visited.add(node)
 
    # 현재 노드 처리
    process(node)
 
    # 인접 노드 방문
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, visited)

2D 그리드 템플릿

def dfs_grid(r, c):
    # 범위 체크
    if r < 0 or r >= rows or c < 0 or c >= cols:
        return
 
    # 방문 체크
    if visited[r][c]:
        return
 
    visited[r][c] = True
 
    # 4방향 탐색
    dfs_grid(r+1, c)
    dfs_grid(r-1, c)
    dfs_grid(r, c+1)
    dfs_grid(r, c-1)

경로 추적 템플릿

def dfs_with_path(node, end, path):
    path.append(node)
 
    if node == end:
        return path
 
    for neighbor in graph[node]:
        if neighbor not in path:
            result = dfs_with_path(neighbor, end, path[:])
            if result:
                return result
 
    return None

DFS vs BFS

특성DFSBFS
자료구조스택 (재귀)큐
탐색 방식깊이 우선너비 우선
최단 경로보장 안 됨보장됨 (가중치 없을 때)
메모리O(h) - 높이O(w) - 너비
활용경로, 사이클, 위상 정렬최단 거리, 레벨 탐색

주의사항

1. 방문 체크 필수

# 무한 루프 방지
visited = set()
if node not in visited:
    visited.add(node)

2. 재귀 깊이 제한

import sys
sys.setrecursionlimit(10**6)  # Python 기본 1000

3. 그리드에서 방향 배열 활용

# 4방향
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
 
for i in range(4):
    nx, ny = x + dx[i], y + dy[i]
    dfs(nx, ny)
 
# 8방향
dx = [0, 0, 1, -1, 1, 1, -1, -1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

그래프 뷰

백링크