템플릿 알고리즘

🧩 템플릿으로 외워두면 코테·백준에서 무적이 되는 알고리즘들

1. DFS (재귀 / 스택)
2. BFS (큐 / 거리 계산 / 다중 시작)
3. Union-Find (서로소 집합)
4. Dijkstra (우선순위 큐 기반 최단경로)
5. DP 템플릿 모음 (1차원, 배낭, 부분합 등)
6. Topological Sort (위상 정렬)
7. Kruskal / Prim (최소 신장 트리)
8. Binary Search (이분 탐색 + 응용: parametric search)
9. Floyd-Warshall (모든 쌍 최단거리)
10. Backtracking (순열 / 조합 / 부분집합)
11. 요약 치트시트 (핵심 포인트 / 복습용)

---

1. DFS (Depth-First Search)

목적: 그래프/격자에서 깊게 탐색(연결 요소, 경로 존재, 백트래킹 등)
핵심 아이디어: 현재 노드에서 갈 수 있는 곳을 재귀(또는 스택)로 끝까지 들어가고, 더 이상 갈 데 없으면 되돌아옴.

재귀 템플릿 (그래프: 인접리스트)

static boolean[] visited;
static ArrayList<Integer>[] graph;

static void dfs(int node) {
    visited[node] = true;
    // 작업: node 방문 시 처리 (ex. count++, print 등)
    for (int nxt : graph[node]) {
        if (!visited[nxt]) dfs(nxt);
    }
}

• 사용처: 연결 요소 개수, 경로 존재 여부, 백트래킹 기반 문제
• 시간: O(V + E), 공간: recursion depth (O(V)) + visited

2D 격자 DFS (미로, 영역 탐색)

static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static boolean[][] visited;
static int N, M;
static int[][] map; // 조건에 따른 값(1이면 방문 가능 등)

static void dfs(int x, int y) {
    visited[x][y] = true;
    // 작업: map[x][y] 처리
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
        if (!visited[nx][ny] && map[nx][ny] == 1) dfs(nx, ny);
    }
}

반복(스택) 버전

Stack<int[]> st = new Stack<>();
st.push(new int[]{sx, sy});
visited[sx][sy] = true;
while (!st.isEmpty()) {
    int[] cur = st.pop();
    // 처리
    for (...) {
        if (!visited[nx][ny] && condition) {
            visited[nx][ny] = true;
            st.push(new int[]{nx, ny});
        }
    }
}

주의점 / 팁

• 재귀 깊이 초과 주의(자바 기본 약 10^4 수준). 깊을 경우 스택 사용하거나 -Xss 옵션, 혹은 반복문으로 변환.
• visited 표시는 들어가자마자(진입 직후) 해야 무한 루프 방지.
• 그래프가 연결되지 않았으면 모든 노드에 대해 for 루프 돌려야 함.

---

2. BFS (Breadth-First Search)

목적: 가까운 노드부터 레벨별 탐색 — 가중치가 같은 그래프에서 최단 거리 보장
핵심: 큐(FIFO)를 사용해 레벨별 확장

기본 템플릿 (그래프)

Queue<Integer> q = new LinkedList<>();
boolean[] visited = new boolean[N+1];
q.add(start);
visited[start] = true;
while (!q.isEmpty()) {
    int cur = q.poll();
    // 처리
    for (int nxt : graph[cur]) {
        if (!visited[nxt]) {
            visited[nxt] = true;
            q.add(nxt);
        }
    }
}

거리 계산 템플릿 (격자 또는 그래프)

int[] dist = new int[N+1];
Arrays.fill(dist, -1);
Queue<Integer> q = new LinkedList<>();
q.add(start);
dist[start] = 0;

while (!q.isEmpty()) {
    int cur = q.poll();
    for (int nxt : graph[cur]) {
        if (dist[nxt] == -1) {
            dist[nxt] = dist[cur] + 1;
            q.add(nxt);
        }
    }
}
// dist[target]이 최단 거리(없으면 -1)

다중 시작점 (토마토, 불 확산 등)

• 초기 큐에 여러 시작점을 넣고 dist[start]=0 하여 동시에 확산시킴.

주의점 / 팁

• 방문 체크는 큐에 넣을 때 해야 함(중복 enqueue 방지).
• 메모리: 큐에 많은 노드가 들어올 수 있음(격자 크기 등 고려).
• BFS는 가중치가 동일할 때만 최단거리. 가중치가 다르면 Dijkstra 사용.

---

3. Union-Find (Disjoint Set)

목적: 집합 합치기 & 같은 집합인지 빠르게 판정 (오프라인 연결성, Kruskal 등)
핵심: 루트(parent) 배열, 경로 압축, union by rank(optional)

템플릿

static int[] parent;

static void makeSet(int n) {
    parent = new int[n+1];
    for (int i = 1; i <= n; i++) parent[i] = i;
}

static int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]); // path compression
}

static void union(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    parent[b] = a; // 혹은 rank 기반으로 합치기
}

복합(랭크 사용)

• rank[] 또는 size[] 사용해 작은 트리를 큰 트리에 붙이면 균형 유지.

주의점

• find의 반환값으로 비교(find(a)==find(b))해야 함.
• 초기화(makeSet) 잊지 않기.

---

4. Dijkstra (우선순위 큐 기반 최단경로)

목적: 가중치(비음수) 그래프의 단일 출발 최단경로
핵심: 우선순위 큐로 현재 최단 후보 정점 선택, 완전최적화 탐색

템플릿

static final int INF = Integer.MAX_VALUE;
static ArrayList<int[]>[] graph; // graph[u] contains {v, cost}
static int[] dist;

static void dijkstra(int start) {
    PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1]-b[1]);
    dist = new int[n+1];
    Arrays.fill(dist, INF);
    dist[start] = 0;
    pq.add(new int[]{start, 0});

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int u = cur[0], d = cur[1];
        if (d > dist[u]) continue; // 이미 더 짧은 경로가 있음
        for (int[] edge : graph[u]) {
            int v = edge[0], w = edge[1];
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.add(new int[]{v, dist[v]});
            }
        }
    }
}

• 시간: O(E log V)

주의점

• 음수 가중치 존재 시 Dijkstra 불가(벨만-포드 사용).
• if (d > dist[u]) continue; 체크 중요(중복 PQ 아이템 무시).

---

5. DP 템플릿 모음 (간단 핵심 패턴)

1) 1차원 점화식 (연속합, 피보나치류)

dp[0] = base;
for (int i = 1; i <= N; i++) {
    dp[i] = f(dp[i-1], dp[i-2], ...); // 문제에 맞게
}

2) 0/1 Knapsack (역방향 1차원 압축)

int[] dp = new int[W+1];
for (int i = 0; i < N; i++) {
    for (int w = W; w >= weight[i]; w--) {
        dp[w] = Math.max(dp[w], dp[w-weight[i]] + value[i]);
    }
}

3) Unbounded Knapsack (무제한)

for (int i = 0; i < N; i++) {
    for (int w = weight[i]; w <= W; w++) {
        dp[w] = Math.max(dp[w], dp[w-weight[i]] + value[i]);
    }
}

4) Subset Sum / Coin Change (방법 수)

dp[0] = 1;
for (int coin : coins) {
    for (int j = coin; j <= target; j++) {
        dp[j] += dp[j-coin];
    }
}

5) 메모이제이션(탑다운)

int[] memo = new int[MAX];
Arrays.fill(memo, -1);
int dfs(int state) {
    if (memo[state] != -1) return memo[state];
    memo[state] = compute(...);
    return memo[state];
}

주의점

• 1차원 압축할 때 전이 방향(역순/정방향)을 꼼꼼히 따질 것.
• 초기값, 불가능 값 처리(-INF, INF, false 등) 잊지 말기.

---

6. Topological Sort (위상 정렬)

목적: DAG에서 순서(선행 조건)를 정하는 알고리즘
템플릿

int[] indeg = new int[N+1];
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= N; i++) if (indeg[i] == 0) q.add(i);

while (!q.isEmpty()) {
    int cur = q.poll();
    order.add(cur);
    for (int nxt : graph[cur]) {
        indeg[nxt]--;
        if (indeg[nxt] == 0) q.add(nxt);
    }
}

• 사용 예: 작업 스케줄, 위상 정렬을 통한 DP(최장 경로 in DAG)

---

7. Kruskal / Prim (MST)

Kruskal (간단)

Collections.sort(edges, (a,b) -> a[2] - b[2]);
makeSet(n);
int total = 0;
for (int[] e : edges) {
    if (find(e[0]) != find(e[1])) {
        union(e[0], e[1]);
        total += e[2];
    }
}

Prim (우선순위 큐 기반)

PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[1]-b[1]);
boolean[] used = new boolean[n+1];
pq.add(new int[]{start, 0});
int total = 0;
while (!pq.isEmpty()) {
    int[] cur = pq.poll();
    if (used[cur[0]]) continue;
    used[cur[0]] = true; total += cur[1];
    for (int[] nxt : graph[cur[0]]) {
        if (!used[nxt[0]]) pq.add(new int[]{nxt[0], nxt[1]});
    }
}

---

8. Binary Search (이분 탐색)

템플릿(정수 배열에서 찾기)

int l = 0, r = n-1;
while (l <= r) {
    int mid = (l + r) >>> 1;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) l = mid + 1;
    else r = mid - 1;
}
return -1;

응용: Parametric Search(가능/불가능 판정)

• while (l <= r)로 mid 잡고, check(mid) 함수로 조건 충족 여부 판단. (ex: 나무 자르기, 공유기 설치)

---

9. Floyd-Warshall (모든 쌍 최단거리)

for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dist[i][j] = (i==j?0:INF);
for edges: dist[u][v]=w;
for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);

• 시간: O(n^3) → n ≤ ~400 정도까지 실용적

---

10. Backtracking (순열/조합/부분집합)

순열

void perm(int idx) {
    if (idx == m) { print(); return; }
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        used[i] = true;
        sel[idx] = arr[i];
        perm(idx+1);
        used[i] = false;
    }
}

조합

void comb(int start, int depth) {
    if (depth == k) { print(); return; }
    for (int i = start; i < n; i++) {
        sel[depth] = arr[i];
        comb(i+1, depth+1);
    }
}

가지치기(Pruning)

• 정렬 + 현재 합 + 남은 최대 합 비교 → 불필요 가지치기 가능

---

11. 요약 치트시트 (외우기용)

• DFS: 재귀, visited 먼저, 재귀 깊이 주의
• BFS: 큐, enqueue 시 visited=true, 거리 dist[cur]+1
• Union-Find: find()에 경로 압축, union()으로 합치기
• Dijkstra: PQ, if (d > dist[u]) continue;
• 0/1 Knapsack: 역방향 for (w = W..wt)
• Unbounded Knapsack / Coin change: 정방향 for (w = wt..W)
• Toposort: indegree 0 → 큐
• Kruskal: 간선 정렬 + union-find
• Binary Search: 범위를 줄이는 check(mid) 패턴
• Floyd: 3중 for (k,i,j)
• Backtracking: 재귀 + visited + 복구(restore)

---

마지막으로 — 암기 & 연습 팁

1. 템플릿은 짧고 자주 복습하세요. 문제 풀 때 바로 붙여넣을 수 있어야 합니다.
2. 작은 예시로 수동 시뮬레이션 해보세요 — 코드가 왜 동작하는지 보이면 기억이 오래갑니다.
3. 한 번에 한 패턴씩 집중 연습: 예) 하루는 BFS 문제 5개, 다음 날 Union-Find 5개.
4. 코테 전에는 Scanner 대신 BufferedReader, StringTokenizer 사용 템플릿을 준비하세요.
5. 실전에서는 오류를 줄이려면 주석 + 변수명을 명확히 해두면 좋습니다.