[C++] 주요 알고리즘 정리 (BFS, DFS, 다익스트라...)

 

시간이 없는 관계로 지삐띠니야의 도움을 빌려 정리햇습니다

---

0) 공통: 방향 배열(격자 탐색)

int dx4[4] = {-1, 0, 1, 0}; // 상 우 하 좌
int dy4[4] = {0, 1, 0, -1};

int dx8[8] = {-1,-1,-1, 0,0, 1,1,1}; // 8방
int dy8[8] = {-1, 0, 1,-1,1,-1,0,1};

---

1) BFS (그래프/격자)

1-1) 그래프 BFS (인접리스트)

#include <vector>
#include <queue>
using namespace std;

// n: 정점 수 (0..n-1), adj: 인접리스트, start: 시작 정점
vector<int> bfs_graph(int n, const vector<vector<int>>& adj, int start) {
    vector<int> dist(n, -1);
    queue<int> q;
    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int nxt : adj[cur]) {
            if (dist[nxt] != -1) continue;
            dist[nxt] = dist[cur] + 1;
            q.push(nxt);
        }
    }
    return dist; // start로부터 최단거리
}

언제 씀? 가중치 없는 최단거리, 레벨 탐색.

---

1-2) 격자 BFS (최단거리)

#include <vector>
#include <queue>
using namespace std;

// 0: 이동 가능, 1: 벽이라고 가정
int bfs_grid_shortest(const vector<vector<int>>& grid, int sx, int sy, int tx, int ty) {
    int n = (int)grid.size();
    int m = (int)grid[0].size();
    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int,int>> q;

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

    int dx[4] = {-1,0,1,0};
    int dy[4] = {0,1,0,-1};

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        if (x == tx && y == ty) return dist[x][y];

        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (grid[nx][ny] == 1) continue;
            if (dist[nx][ny] != -1) continue;

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

언제 씀? 미로 최단거리, 최단 이동 횟수.

---

2) DFS (그래프/격자)

2-1) 그래프 DFS (재귀)

#include <vector>
using namespace std;

void dfs_graph(int cur, const vector<vector<int>>& adj, vector<int>& visited) {
    visited[cur] = 1;
    for (int nxt : adj[cur]) {
        if (!visited[nxt]) dfs_graph(nxt, adj, visited);
    }
}

언제 씀? 연결요소(컴포넌트) 개수, 탐색/순회.

---

2-2) 격자 DFS (영역 개수/섬 개수)

#include <vector>
using namespace std;

void dfs_grid(int x, int y, const vector<vector<int>>& grid, vector<vector<int>>& vis) {
    int n = (int)grid.size();
    int m = (int)grid[0].size();
    vis[x][y] = 1;

    int dx[4] = {-1,0,1,0};
    int dy[4] = {0,1,0,-1};

    for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir], ny = y + dy[dir];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (vis[nx][ny]) continue;
        if (grid[nx][ny] == 0) continue; // 예: 1만 땅, 0은 바다
        dfs_grid(nx, ny, grid, vis);
    }
}

// 사용 예: 섬 개수 세기
int count_components(const vector<vector<int>>& grid) {
    int n = (int)grid.size(), m = (int)grid[0].size();
    vector<vector<int>> vis(n, vector<int>(m, 0));
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1 && !vis[i][j]) {
                cnt++;
                dfs_grid(i, j, grid, vis);
            }
        }
    }
    return cnt;
}

언제 씀? 영역/섬 개수, flood fill.

---

3) 트리 기본 템플릿

3-1) 트리 DFS (부모/깊이 구하기)

#include <vector>
using namespace std;

void tree_dfs(int cur, int parent, const vector<vector<int>>& tree,
              vector<int>& par, vector<int>& depth) {
    par[cur] = parent;
    for (int nxt : tree[cur]) {
        if (nxt == parent) continue;
        depth[nxt] = depth[cur] + 1;
        tree_dfs(nxt, cur, tree, par, depth);
    }
}

언제 씀? 루트 기준 부모/깊이, 서브트리 기반 문제.

---

3-2) 트리 BFS (깊이/부모)

#include <vector>
#include <queue>
using namespace std;

void tree_bfs(int root, const vector<vector<int>>& tree, vector<int>& par, vector<int>& depth) {
    queue<int> q;
    par.assign(tree.size(), -1);
    depth.assign(tree.size(), -1);

    depth[root] = 0;
    q.push(root);

    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int nxt : tree[cur]) {
            if (depth[nxt] != -1) continue;
            par[nxt] = cur;
            depth[nxt] = depth[cur] + 1;
            q.push(nxt);
        }
    }
}

언제 씀? 재귀 싫을 때(스택오버플로 방지), 레벨 기반.

---

4) 이진탐색 (Binary Search)

4-1) 기본 이진탐색(정렬된 배열에서 존재 확인)

#include <vector>
#include <algorithm>
using namespace std;

bool exists_in_sorted(const vector<int>& v, int x) {
    return binary_search(v.begin(), v.end(), x);
}

4-2) lower_bound / upper_bound (개수 세기)

#include <vector>
#include <algorithm>
using namespace std;

// 정렬된 v에서 x의 개수
int count_x(const vector<int>& v, int x) {
    auto lo = lower_bound(v.begin(), v.end(), x);
    auto hi = upper_bound(v.begin(), v.end(), x);
    return (int)(hi - lo);
}

언제 씀? “x 이상 첫 위치”, “x 초과 첫 위치”, 빈도 계산.

---

5) 최단거리: 다익스트라 (가중치 양수)

#include <vector>
#include <queue>
#include <limits>
using namespace std;

vector<long long> dijkstra(int n, const vector<vector<pair<int,int>>>& adj, int start) {
    const long long INF = numeric_limits<long long>::max() / 4;
    vector<long long> dist(n, INF);

    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, cur] = pq.top(); pq.pop();
        if (d != dist[cur]) continue;

        for (auto [nxt, w] : adj[cur]) {
            if (dist[nxt] > dist[cur] + w) {
                dist[nxt] = dist[cur] + w;
                pq.push({dist[nxt], nxt});
            }
        }
    }
    return dist;
}

언제 씀? 간선 가중치가 0 이상(양수 포함)일 때 최단거리.

---