DFS / BFS

14 Mar 2026 • munjjang9

전날 내용 요약 — 탐욕법 (Greedy)

탐욕법 = 매 순간 현재 시점에서 가장 좋은 선택만 하는 전략
적용 조건 두 가지: 탐욕 선택 속성 (현재 최선이 미래 최선을 보장) + 최적 부분 구조 (부분 최적이 모여 전체 최적)
반례가 하나라도 있으면 탐욕 불가 → DP로 전환
패턴 1 — 정렬 후 앞에서 순서대로 선택 (과자 나눠주기)
패턴 2 — 정렬 후 양끝 포인터로 최적 쌍 선택 (구명보트/짐 싣기)
시간복잡도: 정렬이 병목 → 전체 O(N log N)

DFS / BFS란?

지금까지 배운 정렬, 해시, 완전탐색, 탐욕은 주로 1차원 배열에서 동작했다. 하지만 게임에서는 미로 경로 찾기, 연결된 구역 세기, 최단 이동 거리 계산 같은 문제들이 자주 등장한다. 이런 문제들은 그래프 형태로 모델링되고, 이를 탐색하는 두 가지 핵심 방법이 DFS와 BFS다.

DFS (Depth-First Search): 한 방향으로 갈 수 있는 한 최대한 깊이 들어가고, 더 이상 못 가면 돌아와서 다른 방향 탐색
BFS (Breadth-First Search): 가장 가까운 노드부터 먼저 탐색, 거리(레벨) 순서대로 퍼져나감

그래프 표현 방법

그래프는 노드(정점)와 간선(연결)으로 구성된다. 코딩테스트에서는 주로 인접 리스트를 사용한다.

int n = 5; // 노드 수
vector<vector<int>> adj(n);

// 0-1, 0-2, 1-3, 1-4 연결
adj[0] = {1, 2};
adj[1] = {0, 3, 4};
adj[2] = {0};
adj[3] = {1};
adj[4] = {1};

인접 행렬은 O(N²) 공간을 사용하므로 N이 작을 때 (≤ 1,000) 쓰고, 인접 리스트는 O(N + E) 공간으로 N이 클 때 (≤ 100,000) 적합하다. 코테에서는 대부분 인접 리스트를 쓴다.

DFS (깊이 우선 탐색)

0 방문 → 1 방문 → 3 방문 → 막힘 → 되돌아와 4 방문 → 막힘 → 되돌아와 → 2 방문

재귀로 구현하는 게 가장 자연스럽다.

vector<vector<int>> adj;
vector<bool> visited;

void dfs(int node) {
    visited[node] = true;
    cout << node << " ";

    for (int next : adj[node]) {
        if (!visited[next])
            dfs(next);
    }
}

// 사용
int n = 5;
adj.resize(n);
visited.assign(n, false);
// ... 간선 추가 ...
dfs(0); // 0 1 3 4 2

visited 배열 없이 탐색하면 0→1→0→1→… 무한루프에 빠진다. 이미 간 곳은 다시 가지 않는다는 표시가 필수다.

BFS (너비 우선 탐색)

0 방문 → 1, 2 방문 (거리 1) → 3, 4 방문 (거리 2)

BFS는 반드시 큐로 구현한다.

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front(); q.pop();
        cout << node << " ";

        for (int next : adj[node]) {
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
}

// 0 1 2 3 4

visited 체크를 pop할 때 하면 같은 노드가 큐에 여러 번 들어갈 수 있다. push할 때 즉시 visited = true로 설정하는 게 올바른 패턴이다.

최단 거리 — BFS 활용

BFS는 가중치 없는 그래프에서 최단 거리를 보장한다. 레벨 순서로 탐색하기 때문에, 처음 도달했을 때가 항상 최단 거리다.

vector<int> dist(n, -1); // -1 = 미방문

void bfs_dist(int start) {
    queue<int> q;
    q.push(start);
    dist[start] = 0;

    while (!q.empty()) {
        int node = q.front(); q.pop();

        for (int next : adj[node]) {
            if (dist[next] == -1) {
                dist[next] = dist[node] + 1; // 거리 1씩 증가
                q.push(next);
            }
        }
    }
}

dist 배열이 -1이면 미방문이므로, visited 배열을 따로 쓰지 않아도 된다.

2D 격자 탐색 패턴

맵 문제(미로, 섬 세기 등)는 2D 배열을 그래프처럼 탐색한다. 상하좌우 4방향 이동이 “인접 노드” 역할을 한다.

int n, m; // 행, 열
vector<string> grid;

int dx[] = {0, 0, 1, -1}; // 상하좌우 x 변화량
int dy[] = {1, -1, 0, 0}; // 상하좌우 y 변화량

// BFS로 (sx, sy)에서 출발해 (ex, ey)까지 최단 거리
int bfs_grid(int sx, int sy, int ex, int ey) {
    queue<pair<int,int>> q;
    vector<vector<int>> dist(n, vector<int>(m, -1));

    q.push({sx, sy});
    dist[sx][sy] = 0;

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();

        if (x == ex && y == ey) return dist[x][y];

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            // 범위 체크 + 벽 체크 + 미방문 체크
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (grid[nx][ny] == '1') continue; // '1'이 벽
            if (dist[nx][ny] != -1) continue;

            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }
    return -1; // 도달 불가
}

dx/dy 배열 패턴은 2D 탐색 문제에서 거의 매번 등장한다. 외워두는 게 좋다.

DFS vs BFS 비교

기준	DFS	BFS
구현 방식	재귀 or 스택	큐
탐색 순서	깊이 우선	거리(레벨) 순
최단 거리 보장	❌	✅ (가중치 없을 때)
모든 경우 탐색	✅	✅
주요 활용	연결 요소 세기, 경로 존재 여부, 조합 탐색	최단 거리, 최소 이동 횟수

판단 기준

“최단 거리/최소 횟수”가 나오면 → BFS
“경로 존재 여부”, “연결된 영역 세기” → DFS or BFS 모두 가능
“모든 경우 탐색” (완전탐색과 혼합) → DFS

시간복잡도

DFS와 BFS 모두 모든 노드와 간선을 한 번씩 방문하므로 시간복잡도는 동일하다.

구분	시간복잡도
DFS	O(V + E)
BFS	O(V + E)
2D 격자 (N×M)	O(N × M)