Ch.7 그래프

DFS — 깊이 우선 탐색, 끝까지 파고들기

DFS의 동작 원리를 재귀와 스택으로 설명한다방문 체크(visited)의 역할과 필요성을 이해한다DFS를 활용한 경로 탐색과 연결 요소 탐지를 구현한다

미로에서 길을 찾는 가장 직관적인 방법

미로에 들어섰습니다. 갈림길에서 항상 왼쪽부터 선택하고, 막다른 길이면 되돌아갑니다. 이것이 바로 DFS(깊이 우선 탐색)입니다.

되돌아갈 때 어디까지 돌아가야 하지? 이미 방문한 곳을 다시 가면?

스택(또는 재귀 호출 스택)이 되돌아갈 위치를 기억하고, visited 집합이 재방문을 막습니다.

lightbulb

핵심 개념

DFS(깊이 우선 탐색)

한 경로를 끝까지 탐색한 뒤 되돌아가는 방식

백트래킹(Backtracking)

막다른 길에서 이전 갈림길로 되돌아가기

article

핵심 내용

그래프 탐색의 기본 무기, DFS를 배웁니다

DFS는 한 길을 끝까지 가봅니다. 막히면 돌아와서 다른 길을 시도합니다

DFS의 핵심 규칙: 더 깊이 갈 수 있으면 가고, 못 가면 되돌아간다

DFS를 재귀로 구현하면 놀랍도록 간결합니다

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(node)           # 1. 현재 노드 방문
    print(node, end=' ')        # 2. 처리
    
    for neighbor in graph[node]: # 3. 이웃 탐색
        if neighbor not in visited:
            dfs(graph, neighbor, visited)  # 4. 재귀
    
    return visited

# 사용
graph = {'A':['B','C'], 'B':['A','D'], 'C':['A','D'], 'D':['B','C']}
dfs(graph, 'A')  # A B D C

DFS 재귀 템플릿 (암기!) 1. `visited.add(node)` — 방문 표시 2. 현재 노드 처리 3. `for neighbor in graph[node]` — 이웃 순회 4. `if neighbor not in visited` → 재귀 호출

이 4줄 패턴이 면접 그래프 문제의 80%를 해결합니다. 반드시 외우세요!

재귀가 깊어지면 스택 오버플로. 반복문 DFS도 알아야 합니다

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()       # 스택에서 꺼냄
        if node in visited:
            continue
        visited.add(node)
        print(node, end=' ')
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)
    
    return visited

스택에 넣고 → 꺼내고 → 방문 안 했으면 처리 → 이웃을 스택에 추가. BFS와 딱 한 가지만 다릅니다 — stack vs queue

재귀 DFS: 코드가 짧고 직관적 반복 DFS: 스택 오버플로 걱정 없음

재귀 DFS가 어떤 순서로 노드를 방문하는지 추적합니다

방문 순서: A → B → D → (되돌아감) → C 깊이 우선으로 끝까지 갔다 돌아옵니다

DFS의 대표 활용 — 연결 요소(Connected Component) 개수 구하기

def count_components(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    visited = set()
    count = 0
    
    for node in range(n):
        if node not in visited:
            dfs(graph, node, visited)
            count += 1    # DFS 한 번 = 연결 요소 1개
    
    return count

# 0-1-2  3-4  → 2개의 연결 요소
print(count_components(5, [(0,1),(1,2),(3,4)]))  # 2

DFS를 호출한 횟수 = 연결 요소의 개수. 이 패턴은 Number of Islands에도 그대로 적용됩니다!

DFS에서 visited를 사용하지 않으면 어떤 문제가 발생할까요?

재귀 DFS의 시간 복잡도는 O(V + E)이다

DFS 정복 완료!

key

핵심 용어

🔍

DFS

Depth-First Search — 깊이 우선 탐색

📚

스택/재귀

DFS의 핵심 자료구조 — 되돌아갈 위치 기억

✅

visited

이미 방문한 노드를 기록하는 set

edit_note

정리 노트

깊이 우선 탐색 (DFS)

핵심 패턴

재귀 DFS: `visited.add(node)` → 이웃 순회 → 재귀
반복 DFS: stack.pop() → 방문 처리 → 이웃 push
시간 복잡도: O(V + E)

필수 기억

visited: 없으면 사이클에서 무한 루프
연결 요소: DFS 호출 횟수 = 연결 요소 개수

★

DFS 4줄 템플릿: visited.add → 처리 → for neighbor → if not visited → 재귀

image

시각 자료

다이어그램: ds-d54

check_circle

핵심 정리

1DFS = 한 길을 끝까지 탐색 후 되돌아가기
2재귀 DFS 4줄 패턴은 반드시 암기
3visited 없으면 무한 루프, DFS 호출 횟수 = 연결 요소 수

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작