[DFS & BFS]

1. 그래프 기초

그래프란 무엇인가

그래프는 노드(Node, 정점)와 간선(Edge)으로 구성된 자료구조다. 도시와 도로에 비유할 수 있다. 도시가 노드고, 도시를 연결하는 도로가 간선이다. 지하철 노선도, 소셜 네트워크 친구 관계, 웹 페이지 간의 링크가 모두 그래프 구조다.

배열이나 트리와의 차이는 구조의 자유도에 있다. 배열은 순서가 있고, 트리는 부모-자식 관계가 있으며 사이클이 없다. 그래프는 노드 간 연결 방식에 제약이 없어 사이클도 허용한다.

방향 그래프와 무방향 그래프

무방향 그래프:               방향 그래프:
  A --- B                    A --> B
  |     |                    |     |
  C --- D                    v     v
                             C <-- D

무방향 그래프에서 A-B 간선은 A에서 B로도, B에서 A로도 이동할 수 있다. 방향 그래프에서 A→B 간선은 A에서 B로만 이동할 수 있다. 양방향 도로는 무방향, 일방통행은 방향 그래프에 해당한다.

가중 그래프와 비가중 그래프

비가중 그래프:        가중 그래프:
  A --- B              A --5-- B
  |     |              |       |
  C --- D              3       2
                       |       |
                       C --7-- D

간선에 가중치(비용, 거리, 시간)가 있는 그래프를 가중 그래프라고 한다. 비가중 그래프에서는 모든 간선이 동일한 비용이라고 본다. 비가중 그래프에서 최단 경로는 BFS로 구할 수 있다. 가중 그래프에서는 다익스트라(Dijkstra) 알고리즘이 필요하다.

인접 리스트와 인접 행렬

그래프를 코드로 표현하는 방법은 두 가지다.

인접 리스트: 각 노드에서 연결된 노드들의 목록을 저장한다.

graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6],
    4: [],
    5: [],
    6: []
}

인접 행렬: n×n 크기의 2차원 배열로, matrix[i][j] = 1이면 i에서 j로 가는 간선이 있다는 것을 나타낸다.

n = 4
matrix = [[0] * n for _ in range(n)]
matrix[0][1] = 1
matrix[1][0] = 1
matrix[1][2] = 1
matrix[2][1] = 1

두 방식의 차이는 다음과 같다.

항목	인접 리스트	인접 행렬
공간 복잡도	O(V + E)	O(V²)
특정 간선 존재 확인	O(degree)	O(1)
모든 이웃 순회	O(degree)	O(V)
적합한 경우	간선이 적은 희소 그래프	간선이 많은 밀집 그래프

코딩 테스트에서는 대부분 인접 리스트를 사용한다. 노드 수가 수천 개인 희소 그래프에서 인접 행렬을 쓰면 메모리 낭비가 크다.

2. DFS (깊이 우선 탐색)

DFS 원리

DFS는 한 방향으로 갈 수 있는 끝까지 탐색한 뒤, 막히면 가장 최근 갈림길로 돌아와 다른 방향을 시도하는 탐색 방식이다.

미로를 탐색한다고 생각해보자. 갈림길에서 한 방향을 선택하고, 막힐 때까지 직진한다. 막히면 마지막 갈림길로 되돌아와서 아직 탐색하지 않은 방향을 고른다. 이것을 모든 갈림길에서 반복하면 전체 미로를 탐색할 수 있다.

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

DFS(1) 탐색 순서:
1 → 2 → 4 (막힘, 4에서 이웃 없음)
      → 5 (막힘, 5에서 이웃 없음)
  → 3 → 6 (막힘, 6에서 이웃 없음)
결과: 1, 2, 4, 5, 3, 6

재귀 구현

재귀 DFS는 콜 스택이 "갈림길 기록"을 대신한다. 함수 호출마다 현재 노드 정보가 스택에 쌓이고, 함수가 반환될 때 이전 위치로 돌아간다.

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    result = [start]
    for neighbor in graph[start]:
        if neighbor not in visited:
            result.extend(dfs_recursive(graph, neighbor, visited))
    return result

graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6],
    4: [],
    5: [],
    6: []
}

print(dfs_recursive(graph, 1))

출력:

[1, 2, 4, 5, 3, 6]

스택 구현

재귀 깊이 한도를 초과할 위험이 있을 때 명시적 스택을 사용한다. 재귀 호출의 콜 스택을 직접 관리하는 방식이다.

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    result = []
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        result.append(node)
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)
    return result

print(dfs_iterative(graph, 1))

출력:

[1, 2, 4, 5, 3, 6]

reversed로 이웃 목록을 뒤집어 스택에 넣는 이유는 스택이 LIFO이기 때문이다. 첫 번째 이웃이 마지막에 들어가야 가장 먼저 꺼내진다. 재귀 DFS와 동일한 탐색 순서를 유지하려면 이 처리가 필요하다.

방문 처리 방법

DFS에서 방문한 노드를 기록하지 않으면 사이클이 있는 그래프에서 무한 루프에 빠진다. 방문 처리 방법은 상황에 따라 세 가지를 선택한다.

set 사용: 방문 여부를 O(1)로 확인할 수 있다. 가장 일반적인 방법이다.
배열 사용: 노드가 정수 인덱스인 경우 visited = [False] * (n + 1). 메모리 접근이 빠르다.
입력 배열 수정: 2D 격자에서 방문한 칸을 0 등으로 변경한다. 별도 배열이 필요 없다.

2차원 격자에서의 DFS -- 섬의 개수

미로 탐색, 섬의 개수 세기 등 2D 격자 문제에서 DFS가 자주 쓰인다. 상하좌우 방향 배열을 미리 정의해두면 코드가 간결해진다.

격자:
  1 1 0 0
  1 0 0 1
  0 0 1 1
  0 0 1 0

육지(1)로 이루어진 섬 탐색:
  좌표 (0,0)에서 DFS 시작
  → (0,0), (0,1), (1,0) 방문 → 첫 번째 섬
  좌표 (1,3)에서 DFS 시작
  → (1,3), (2,2), (2,3), (3,2) 방문 → 두 번째 섬
  섬의 개수: 2

import sys
sys.setrecursionlimit(10**5)

def count_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    island_count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if visited[r][c] or grid[r][c] == 0:
            return
        visited[r][c] = True
        for dr, dc in directions:
            dfs(r + dr, c + dc)

    for r in range(rows):
        for c in range(cols):
            if not visited[r][c] and grid[r][c] == 1:
                dfs(r, c)
                island_count += 1

    return island_count

grid = [
    [1, 1, 0, 0],
    [1, 0, 0, 1],
    [0, 0, 1, 1],
    [0, 0, 1, 0]
]
print(count_islands(grid))

출력:

directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]은 각각 위, 아래, 왼쪽, 오른쪽을 나타낸다. sys.setrecursionlimit은 Python의 기본 재귀 한도(1000)가 BOJ 문제 대부분을 통과하지 못하기 때문에 코드 상단에서 설정해 두는 것이다. 10**5 이상으로 설정한다.

3. BFS (너비 우선 탐색)

BFS 원리

BFS는 시작 노드에서 가까운 노드부터 층위별로 순서대로 탐색하는 방식이다.

돌을 연못에 던지면 파문이 동심원 형태로 퍼져나가는 것과 같다. 시작점에서 거리 1인 모든 노드를 먼저 방문하고, 그다음 거리 2인 모든 노드를 방문한다.

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

BFS(1) 탐색 순서:
거리 0: [1]
거리 1: [2, 3]
거리 2: [4, 5, 6]
결과: 1, 2, 3, 4, 5, 6

DFS는 깊이 방향으로 최대한 파고들고, BFS는 너비 방향으로 층위별로 퍼져나간다. 이 성질 덕분에 BFS는 비가중 그래프에서 최단 거리(간선 수 기준)를 자연스럽게 보장한다.

deque를 이용한 구현

BFS는 큐(Queue)로 구현한다. 방문할 노드를 큐에 넣고, 앞에서 하나씩 꺼내며 이웃을 큐에 추가한다. Python에서는 collections.deque를 사용한다. 리스트의 pop(0)은 O(n)이지만 deque의 popleft()는 O(1)이다.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return result

graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6],
    4: [],
    5: [],
    6: []
}

print(bfs(graph, 1))

출력:

[1, 2, 3, 4, 5, 6]

DFS와 달리 BFS에서는 큐에 넣을 때 방문 처리를 해야 한다. 꺼낼 때 처리하면 같은 노드가 큐에 여러 번 들어갈 수 있다. 같은 노드가 여러 번 큐에 쌓이면 불필요한 탐색이 반복되어 시간 초과가 날 수 있다.

최단 거리 탐색

BFS가 층위별로 탐색한다는 성질 덕분에, 시작 노드에서 각 노드까지의 최단 거리를 자동으로 구할 수 있다. 거리 딕셔너리를 함께 관리한다.

시작: 노드 1
     1 → 2: 거리 1
     1 → 3: 거리 1
     2 → 4: 거리 2
     2 → 5: 거리 2
     3 → 6: 거리 2

from collections import deque

def bfs_shortest(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in dist:
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)
    return dist

print(bfs_shortest(graph, 1))

출력:

{1: 0, 2: 1, 3: 1, 4: 2, 5: 2, 6: 2}

dist에 키가 없으면 미방문 상태다. 딕셔너리가 방문 처리와 거리 기록을 동시에 담당하는 것이다.

2차원 격자에서의 BFS -- 미로 최단 거리

격자에서 BFS는 특정 출발점에서 각 칸까지의 최단 거리를 구하는 데 사용한다. 거리 배열을 -1로 초기화하고, 방문할 때 이전 칸의 거리 + 1로 갱신한다.

미로:
  S 1 0 1
  1 1 0 1
  0 1 1 E
  (S: 시작, E: 끝, 0: 벽, 1: 통로)

BFS로 최단 경로 거리 계산:
  dist[0][0] = 0  (S)
  dist[0][1] = 1
  dist[1][0] = 1
  dist[1][1] = 2
  dist[2][1] = 3
  dist[2][2] = 4
  dist[2][3] = 5  (E)
  최단 거리: 5

from collections import deque

def bfs_grid_shortest(grid, start_r, start_c, end_r, end_c):
    rows, cols = len(grid), len(grid[0])
    dist = [[-1] * cols for _ in range(rows)]
    dist[start_r][start_c] = 0
    queue = deque([(start_r, start_c)])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while queue:
        r, c = queue.popleft()
        if r == end_r and c == end_c:
            return dist[r][c]
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1 and grid[nr][nc] == 1:
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))

    return -1

grid = [
    [1, 1, 0, 1],
    [1, 1, 0, 1],
    [0, 1, 1, 1]
]
print(bfs_grid_shortest(grid, 0, 0, 2, 3))

출력:

dist[nr][nc] == -1 조건이 방문 여부 확인을 겸한다. 별도의 visited 배열이 필요 없다.

4. DFS vs BFS 비교

탐색 순서 비교

같은 그래프에서 두 알고리즘의 탐색 순서를 나란히 보면 차이가 명확하다.

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

DFS 탐색 순서:               BFS 탐색 순서:
1 → 2 → 4 (백트랙)          1 → (거리 1: 2, 3)
      → 5 (백트랙)               → (거리 2: 4, 5, 6)
  → 3 → 6 (백트랙)
결과: 1, 2, 4, 5, 3, 6      결과: 1, 2, 3, 4, 5, 6
(깊이 방향, 한 경로 완전 탐색)  (너비 방향, 층위별 탐색)

DFS는 노드 2를 방문한 직후 4, 5까지 끝까지 파고든 뒤 3으로 넘어간다. BFS는 노드 1의 모든 이웃(2, 3)을 먼저 방문하고 나서 그 다음 층위(4, 5, 6)로 넘어간다.

선택 기준

최단 경로가 필요하면 BFS를 선택한다.

비가중 그래프에서 출발점에서 목표점까지의 최단 경로(간선 수 최소)가 필요하다면 BFS가 답이다. BFS는 층위별로 탐색하기 때문에, 처음 목표점에 도달한 순간이 최단 거리다. DFS로 목표점을 먼저 찾더라도 그것이 최단 경로라는 보장이 없다.

모든 경우를 탐색해야 하면 DFS를 선택한다.

가능한 모든 경로, 모든 조합, 경로의 존재 여부 등을 탐색해야 할 때는 DFS가 적합하다. 재귀로 작성하기 자연스럽고, 백트래킹과 결합하기 쉽다. 5주차에서 다룬 완전 탐색과 백트래킹이 모두 DFS 기반이다.

연결 요소 탐색은 둘 다 가능하다.

섬의 개수 세기처럼 연결된 노드들을 하나의 집합으로 묶는 문제는 DFS와 BFS 모두 사용할 수 있다. 코드 작성이 더 익숙한 방식을 선택하면 된다.

비교 정리표

항목	DFS	BFS
자료구조	스택 (재귀 콜 스택 또는 명시적 스택)	큐 (deque)
탐색 방향	깊이 방향, 한 경로를 끝까지	너비 방향, 층위별
최단 거리 보장	보장하지 않는다	보장한다 (비가중 그래프)
시간 복잡도	O(V + E)	O(V + E)
공간 복잡도	O(V) -- 재귀 깊이 또는 스택 크기	O(V) -- 큐 최대 크기
적합한 문제	경로 탐색, 백트래킹, 연결 요소	최단 거리, 층위별 탐색, 연결 요소
방문 처리 시점	노드를 꺼낼 때	큐에 넣을 때

5. 시간 복잡도 정리

알고리즘	시간 복잡도	공간 복잡도	비고
DFS (인접 리스트)	O(V + E)	O(V)	V: 노드 수, E: 간선 수
DFS (인접 행렬)	O(V²)	O(V)	모든 이웃 확인에 O(V)
BFS (인접 리스트)	O(V + E)	O(V)	큐 최대 크기 O(V)
BFS (인접 행렬)	O(V²)	O(V)	모든 이웃 확인에 O(V)

DFS와 BFS 모두 인접 리스트를 사용하면 O(V + E)다. 각 노드를 정확히 한 번 방문하고(O(V)), 각 간선을 정확히 두 번 확인하기(무방향 그래프, O(E)) 때문이다. 인접 행렬에서는 노드 하나의 이웃 전체를 확인하는 데 O(V)가 필요하므로, 전체 시간 복잡도가 O(V²)이 된다.

6. Python 메서드 정리

메서드	용도	예시
`sys.setrecursionlimit(n)`	재귀 한도 설정	`sys.setrecursionlimit(10**5)`
`set.add(x)` / `x in set`	방문 처리, O(1) 확인	`visited.add(node)`
`collections.deque([start])`	BFS 큐 초기화	`queue = deque([1])`
`deque.popleft()`	큐 앞에서 꺼내기, O(1)	`node = queue.popleft()`
`deque.append(x)`	큐 뒤에 넣기, O(1)	`queue.append(neighbor)`
`reversed(iterable)`	스택 DFS 방문 순서 보정	`reversed(graph[node])`
`defaultdict(list)`	동적 인접 리스트 구성	`graph[u].append(v)`

7. 연습 문제

입문

번호	문제	난이도	링크	핵심 접근
2606	바이러스	실버 3	https://www.acmicpc.net/problem/2606	1번 노드에서 DFS, 연결된 노드 수 세기
11724	연결 요소의 개수	실버 2	https://www.acmicpc.net/problem/11724	미방문 노드에서 DFS마다 카운터 증가
1260	DFS와 BFS	실버 2	https://www.acmicpc.net/problem/1260	인접 리스트 구성 후 DFS와 BFS 모두 구현, 번호 작은 노드부터 방문

핵심

번호	문제	난이도	링크	핵심 접근
2667	단지번호붙이기	실버 1	https://www.acmicpc.net/problem/2667	격자 DFS로 연결 요소 탐색, 각 요소의 크기 기록
2178	미로 탐색	실버 1	https://www.acmicpc.net/problem/2178	BFS 격자 최단 거리, 거리 배열 패턴
7576	토마토	골드 5	https://www.acmicpc.net/problem/7576	다중 출발 BFS, 처음부터 익은 토마토 모두 큐에 삽입

프로그래머스

문제	난이도	링크	핵심 접근
타겟 넘버	Lv 2	https://school.programmers.co.kr/learn/courses/30/lessons/43165	재귀 DFS로 +/- 모든 경우 탐색
게임 맵 최단거리	Lv 2	https://school.programmers.co.kr/learn/courses/30/lessons/1844	BFS 격자 최단 거리 탐색

'CodingTest > 자료구조-알고리즘' 카테고리의 다른 글

[재귀 & 완전 탐색] & [백트래킹] (0)	2026.03.24
해시 (Hash) (1)	2026.03.17
큐 (Queue) (1)	2026.03.17
스택 (Stack) (0)	2026.03.17
연결 리스트 (Linked List) (0)	2026.03.16