코스

그래프 이론

탐색·최단경로·유량·매칭·연결성.

Level 2 → Level 9 94 아이템 34 문제 60 강의 0 확인 문제

코스 진행도 0%

0 / 94 아이템 완료

Level 2 · Solver

Solver

그래프 이론 · Solver 단계

0/10 완료

Lesson 깊이 우선 탐색의 원리 필수 8m 현재

DFS란?

DFS(Depth-First Search, 깊이 우선 탐색) 는 그래프나 트리를 탐색할 때 한 길을
끝까지 파고든 뒤, 막다른 곳에서 되돌아와 다른 길을 탐색하는 방식입니다.

미로에서 한쪽 벽을 손으로 짚고 갈 수 있는 데까지 간 다음, 막히면 갈림길로 돌아와
다른 길을 시도하는 것과 같습니다.

1. 그래프 표현부터

탐색하려면 먼저 그래프를 메모리에 담아야 합니다. 가장 흔한 표현은 인접 리스트
입니다 — 각 정점마다 "이어진 정점들의 목록"을 둡니다.

정점 1 → [2, 3]
정점 2 → [1, 4]
정점 3 → [1]
정점 4 → [2]

간선이 적은 희소 그래프에서는 인접 행렬( $$O(V^2)$$ 메모리)보다 인접 리스트
( $$O(V + E)$$ )가 효율적입니다.

2. DFS의 동작

한 정점에서 출발해:

현재 정점을 방문 표시한다.
이어진 정점 중 아직 방문 안 한 곳으로 깊이 들어간다(재귀).
더 갈 곳이 없으면 되돌아온다.

이 "끝까지 갔다가 되돌아오는" 흐름이 재귀와 완벽히 맞아떨어집니다. 그래서 DFS는
보통 재귀로 구현합니다.

3. 방문 표시가 생명

방문 배열을 안 쓰면 같은 정점을 무한히 오갈 수 있습니다(사이클). 방문하면 즉시
표시하고, 표시된 곳은 다시 안 들어간다 — 이것이 DFS의 정확성과 종료를
보장합니다. 각 정점을 한 번씩만 방문하므로 전체 복잡도는 $$O(V + E)$$ 입니다.

4. DFS로 푸는 문제들

문제	DFS의 역할
연결 요소 세기	한 번의 DFS = 한 덩어리
경로 존재 여부	출발에서 도착에 닿는가
사이클 탐지	탐색 중인 정점을 다시 만나면 사이클
위상 정렬	DFS 종료 순서의 역순
미로 탐색/영역 칠하기(flood fill)	격자를 그래프로 보고 DFS

특히 격자(2차원 배열)에서 "연결된 영역의 크기/개수"를 구하는 flood fill이 가장
자주 나옵니다.

5. DFS vs BFS

둘 다 모든 정점을 $$O(V+E)$$ 에 방문하지만 성격이 다릅니다.

	DFS	BFS
자료구조	스택(재귀)	큐
진행 방향	깊이 우선	너비 우선
최단 거리	보장 안 됨	보장됨(무가중치)
적합	경로·연결성·사이클	최단 거리·레벨

"최단 거리"가 필요하면 BFS, "갈 수 있나/연결됐나/모든 경로"면 DFS가 자연스럽습니다.

정리

DFS는 한 길을 끝까지 파고들고 막히면 되돌아오는 탐색입니다. 인접 리스트로
그래프를 담고, 방문 표시로 사이클을 막으며, 재귀로 간결하게 구현합니다.
연결 요소·경로·사이클·flood fill의 기본 도구입니다.

Lesson DFS 구현: 재귀와 명시적 스택 선택 8m

DFS를 코드로

재귀 DFS, flood fill, 그리고 깊이가 깊을 때를 위한 반복 DFS를 다룹니다.

1. 그래프 입력과 재귀 DFS

vector<int> adj[100001];      // 인접 리스트
bool visited[100001];

void dfs(int u) {
    visited[u] = true;        // 방문 즉시 표시
    // u 처리
    for (int v : adj[u])
        if (!visited[v])
            dfs(v);           // 안 가본 이웃으로 깊이 들어감
}

int main() {
    // 간선 입력 (무방향이면 양쪽 다)
    // for each edge (a, b): adj[a].push_back(b); adj[b].push_back(a);
    for (int i = 1; i <= n; i++)
        if (!visited[i]) dfs(i);   // 연결 요소마다 한 번씩
}

import sys
sys.setrecursionlimit(300000)     # 깊은 DFS 대비 필수!

adj = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)

def dfs(u):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(v)

for i in range(1, n+1): if not visited[i]: dfs(i)로 모든 정점을 돌면
연결 요소의 개수도 셀 수 있습니다.

2. Flood Fill (격자 DFS)

격자에서 상하좌우로 연결된 영역을 탐색합니다.

int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int board[1001][1001];
bool vis[1001][1001];

void fill(int x, int y) {
    vis[x][y] = true;
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;  // 격자 밖
        if (vis[nx][ny] || board[nx][ny] == 0) continue;        // 방문/벽
        fill(nx, ny);
    }
}

dx, dy 방향 배열로 네 방향을 깔끔하게 순회하는 것이 표준 관용구입니다.

3. 깊이가 깊으면: 명시적 스택 DFS

정점이 $$10^5$$ 개 일렬로 이어진 그래프는 재귀 깊이가 너무 깊어 스택 오버플로가
날 수 있습니다(특히 파이썬). 그럴 땐 스택으로 직접 구현합니다.

void dfs(int start) {
    stack<int> st;
    st.push(start);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (visited[u]) continue;
        visited[u] = true;
        // u 처리
        for (int v : adj[u])
            if (!visited[v]) st.push(v);
    }
}

def dfs(start):
    st = [start]
    while st:
        u = st.pop()
        if visited[u]:
            continue
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                st.append(v)

방문 표시 시점이 재귀와 미묘하게 다르니(꺼낼 때 표시), 중복 push를 허용하고
꺼낼 때 거르는 방식으로 짭니다.

4. 흔한 실수

방문 표시 누락/지연 — 사이클이 있으면 무한 루프. 방문 즉시 표시.
파이썬 재귀 한도 — setrecursionlimit 안 하면 깊은 그래프에서 RecursionError.
무방향 그래프 단방향 입력 — adj[a], adj[b] 둘 다 넣어야 함.
격자 경계 검사 — 인덱스 범위를 먼저 확인하지 않으면 런타임 에러.
연결 요소 빠뜨림 — 시작 정점 하나만 DFS하면 떨어진 덩어리를 놓침.

5. 패턴 알아보기

"연결된 영역/덩어리 개수·크기" → flood fill DFS.
"A에서 B로 갈 수 있나" → DFS 도달 가능성.
"사이클이 있나" → DFS 중 회색 정점 재방문 확인.
최단 거리는 DFS가 아니라 BFS — 헷갈리지 마세요.

Lesson 실전 가이드 — DFS를 고르는 기준과 함정 선택 8m

실전에서 DFS 문제 알아보기

탐색 문제 앞에서 "DFS냐 BFS냐"를 고민하게 됩니다. DFS가 자연스러운 문제의
모양과, 깊이 제한이라는 DFS 특유의 함정을 정리합니다.

1. 출제 신호

연결 요소 개수 — "단지 수", "섬의 개수". 모든 정점을 돌며 미방문이면
새 컴포넌트로 세는 구조라 DFS가 가장 짧게 짜집니다.
사이클 존재 판정, "다시 자기 자신으로 돌아올 수 있는가".
경로의 존재/모양 — "한 줄로 끝까지 들어갔다가 되돌아오는" 서술.
트리에서 서브트리 단위 계산 — 자식의 답을 모아 부모의 답을 만드는
구조(후위 처리)는 DFS 그 자체입니다.
반대로 "최단", "최소 횟수" 가 보이면 DFS가 아니라 BFS입니다. 이 구분이
이 단원에서 가장 중요한 한 줄입니다.

2. 풀이 결정 절차

그래프를 만듭니다 — 인접 리스트(정점·간선형) 또는 격자 + 방향 배열.
방문 표시 시점을 정합니다 — 함수에 들어가자마자(또는 호출 직전) 표시.
재귀 깊이를 가늠합니다 — 정점이 $$10^5$$ 이상이면 한 줄로 늘어선
그래프에서 깊이가 $$N$$ 까지 갑니다. 파이썬은 한도 조정 또는 스택 변환,
C++도 스택 크기를 의식하세요.
컴포넌트 문제라면 바깥 루프(모든 정점에 대해 미방문이면 DFS 시작)를
잊지 않습니다.

3. 자주 하는 실수

무방향 그래프에서 부모로 되돌아가 사이클 오탐. 간선 $$(u, v)$$ 를 양쪽에
넣었으므로, 사이클 판정 시 "직전에 온 정점"은 제외해야 합니다.

bool dfs(int u, int parent) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (v == parent) continue;          // 왔던 길은 사이클이 아니다
        if (visited[v]) return true;        // 진짜 사이클
        if (dfs(v, u)) return true;
    }
    return false;
}

방문 표시를 너무 늦게. 표시 전에 같은 정점이 여러 경로로 호출되면
지수적으로 느려집니다. 들어가자마자 표시가 원칙입니다.
파이썬 재귀 한도. 기본 약 1000이라 $$N = 10^5$$ 그래프에서
RecursionError가 납니다. sys.setrecursionlimit(10**6) 또는 명시적
스택으로 변환하세요.
격자에서 방향 배열 오타. dx, dy 네 방향 중 하나를 빠뜨리거나
부호가 틀리는 고전적 실수 — 항상 같은 상수 쌍을 복사해 쓰는 자기만의
템플릿을 만드세요.
컴포넌트 세기에서 바깥 루프 누락. 1번 정점에서 한 번만 DFS하면 다른
컴포넌트를 영영 못 봅니다.

4. 연습 방법

이 페이지 오른쪽의 추천 문제는 쉬운 순 → 어려운 순입니다. 격자
컴포넌트 세기부터 시작해 인접 리스트 그래프, 사이클·트리 문제로 이어집니다.

같은 문제를 재귀와 명시적 스택 두 가지로 한 번씩 짜 보면 깊이 제한 이슈에
대한 감각이 생깁니다. 3문제 이상 풀어 클리어하면 레이팅의
CLASS 보너스에 반영됩니다.

Practice problem 택배 운송 선택 25m

KOI00007

택배 운송

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Practice problem 연결 요소의 개수 선택 25m

R00734

연결 요소의 개수

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

실버 I 지금 풀기

Lesson 너비 우선 탐색과 최단 거리 필수 8m

BFS란?

BFS(Breadth-First Search, 너비 우선 탐색) 는 시작점에서 가까운 정점부터
차례로 탐색하는 방법입니다. 거리 1인 정점을 모두 본 뒤 거리 2, 그다음 거리 3...
이렇게 물결이 퍼지듯 동심원으로 넓혀 갑니다.

이 성질 덕분에 BFS는 가중치 없는 그래프의 최단 거리를 구하는 표준 도구입니다.

1. 큐가 핵심 부품

BFS는 큐(FIFO) 로 구현합니다. 큐의 "먼저 들어온 것이 먼저 나온다"는 성질이
"가까운 정점을 먼저 처리한다"를 자동으로 보장합니다.

시작 정점을 큐에 넣고 방문 표시.
큐에서 하나 꺼내, 이어진 정점 중 안 가본 곳을 모두 큐에 넣고 표시.
큐가 빌 때까지 반복.

거리 $$d$$ 인 정점들이 큐에서 모두 빠진 뒤에야 거리 $$d+1$$ 인 정점들이 처리됩니다.

2. 최단 거리가 보장되는 이유

BFS는 정점을 거리 순서대로 방문합니다. 어떤 정점에 처음 도달했을 때의
거리가 곧 최단 거리입니다 — 더 짧은 경로가 있었다면 그 경로로 먼저 도달했을
테니까요.

그래서 BFS는 "한 출발점에서 모든 정점까지의 최단 거리(간선 수)"를 $$O(V + E)$$ 에
한 번에 구합니다. 단, 모든 간선의 가중치가 같을 때만 성립합니다. 가중치가
다르면 다익스트라가 필요합니다.

3. 거리 배열로 방문과 거리를 동시에

방문 여부와 거리를 따로 관리할 필요 없이, dist 배열 하나로 둘 다 처리하는 것이
깔끔합니다.

dist[시작] = 0
이웃 v가 아직 -1(미방문)이면: dist[v] = dist[현재] + 1

dist[v] != -1이면 이미 방문한 것이니, 별도 방문 배열이 필요 없습니다.

4. BFS로 푸는 대표 문제

문제	BFS 활용
미로 최단 경로	격자 BFS, 칸 = 정점
최소 이동 횟수	한 번 이동 = 간선 하나
그래프 거리/레벨	시작점에서의 거리
다중 시작점 전파(불·물 번짐)	여러 점을 동시에 큐에
이분 그래프 판정	레벨로 두 색 칠하기

특히 격자 미로의 최단 거리가 BFS의 간판 문제입니다.

5. 변형: 0-1 BFS, 다중 시작점

다중 시작점 BFS: 처음에 여러 정점을 동시에 큐에 넣으면, 가장 가까운
시작점까지의 거리를 한 번에 구합니다(예: 여러 곳에서 동시에 번지는 불).
0-1 BFS: 가중치가 0과 1뿐이면, 덱을 써서 0짜리는 앞에, 1짜리는 뒤에 넣어
다익스트라 없이 최단 거리를 구합니다.

정리

BFS는 가까운 곳부터 물결처럼 퍼지는 탐색이며, 큐로 구현합니다. 가중치 없는
그래프의 최단 거리를 $$O(V+E)$$ 에 구하는 것이 핵심 용도입니다. 다음 강의에서
미로 BFS를 코드로 완성합니다.

Lesson BFS 구현과 격자 미로 최단 경로 선택 8m

BFS를 코드로

기본 BFS와 가장 자주 나오는 격자 미로 최단 경로를 구현합니다.

1. 기본 그래프 BFS (최단 거리)

vector<int> adj[100001];
int dist[100001];

void bfs(int start) {
    fill(dist, dist + n + 1, -1);   // -1 = 미방문
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {           // 처음 도달 = 최단
                dist[v] = dist[u] + 1;
                q.push(v);                 // 넣을 때 표시 (front에서 X)
            }
        }
    }
}

from collections import deque

def bfs(start, n, adj):
    dist = [-1] * (n + 1)
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

핵심: 큐에 넣을 때 방문 표시(거리 기록)를 합니다. 꺼낼 때 표시하면 같은
정점이 큐에 여러 번 들어가 비효율적이거나 거리가 틀립니다.

2. 격자 미로 최단 경로

int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int maze[1001][1001], dist[1001][1001];

int bfs(int sx, int sy, int ex, int ey) {
    queue<pair<int,int>> q;
    dist[sx][sy] = 1;            // 시작 칸도 1로 세는 문제 관례면
    q.push({sx, sy});
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;  // 밖
            if (dist[nx][ny] || maze[nx][ny] == 0) continue;        // 방문/벽
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }
    return dist[ex][ey];
}

def bfs(sx, sy, n, m, maze):
    dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
    dist = [[0] * m for _ in range(n)]
    dist[sx][sy] = 1
    q = deque([(sx, sy)])
    while q:
        x, y = q.popleft()
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if 0 <= nx < n and 0 <= ny < m and not dist[nx][ny] and maze[nx][ny]:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))
    return dist

3. 다중 시작점 BFS

여러 출발점에서 동시에 퍼질 때는, 처음에 그 모든 점을 큐에 넣고 거리 0(또는 1)로
표시한 뒤 평소처럼 BFS합니다. 그러면 각 칸은 가장 가까운 시작점까지의 거리를
얻습니다(토마토 익히기, 불 번짐 등).

for (auto [x, y] : sources) { dist[x][y] = 0; q.push({x, y}); }
// 이후 동일한 BFS

4. 흔한 실수

꺼낼 때 방문 표시 — 같은 정점이 큐에 중복으로 들어가 거리가 틀리거나 느려짐.
넣을 때 표시하세요.
거리 기준 혼동 — "시작 칸 포함 칸 수"인지 "이동 횟수"인지에 따라 초기값과
답이 1 차이. 문제 정의 확인.
파이썬 리스트로 큐 — pop(0)는 $$O(N)$$ . deque.popleft() 필수.
격자 경계 검사 빠뜨림 — 인덱스 범위 먼저 확인.
가중치 다른 그래프에 BFS — 최단 거리 틀림. 다익스트라로.

5. 패턴 알아보기

"최소 이동/최단 거리" + 모든 간선 비용 동일 → BFS.
"미로/격자에서 최단 경로" → 격자 BFS.
"여러 곳에서 동시에 번진다" → 다중 시작점 BFS.
비용이 제각각이면 BFS가 아니라 다익스트라.

Lesson 실전 가이드 — 최단·최소가 보이면 BFS 선택 8m

실전에서 BFS 문제 알아보기

BFS 문제의 90%는 한 문장으로 요약됩니다 — "모든 이동의 비용이 같을 때
최소 횟수". 이 신호를 다양한 변장 속에서 알아보는 것이 이 단원입니다.

1. 출제 신호

"최단 거리", "최소 횟수", "가장 빨리" + 한 번의 이동 비용이 전부 동일 —
미로 탈출, 숨바꼭질( $$+1$$ , $$-1$$ , $\times 2$ ).
상태 전이 퍼즐 — 물통 붓기, 버튼 눌러 숫자 만들기. "칸"이 아니라
상태가 정점이라는 점만 다를 뿐 같은 BFS입니다.
다중 시작점 — "모든 토마토에서 동시에 퍼진다", "여러 발화점". 시작점을
전부 큐에 넣고 시작하면 끝입니다.
단계(레벨) 수 자체가 답 — "며칠 걸리는가".
이동 비용이 0과 1로 섞이거나 제각각이면 BFS가 아니라 0-1 BFS·다익스트라
(다음 단계)임을 기억하세요.

2. 풀이 결정 절차

상태를 정의합니다 — 위치만으로 충분한가, 추가 정보(벽 부순 횟수,
열쇠 보유 등)가 필요한가? 추가 정보가 답에 영향을 주면 상태에 넣어야 합니다.
이동 비용이 전부 1인지 확인합니다 — 아니라면 BFS로는 안 됩니다.
dist 배열을 $$-1$$ 로 초기화해 방문 표시를 겸하게 합니다.
시작 상태(들)를 모두 큐에 넣고, 꺼낸 순서가 곧 거리 오름차순임을 이용해
목표 도달 즉시 답을 확정합니다.

3. 자주 하는 실수

방문 표시를 큐에서 꺼낼 때 함. 같은 상태가 큐에 수십 번 중복으로 들어가
메모리·시간이 폭발합니다. 넣을 때 표시가 BFS의 제1원칙입니다.

queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : next_states(u)) {
        if (dist[v] != -1) continue;   // 이미 큐에 들어간 상태
        dist[v] = dist[u] + 1;         // push 시점에 거리 확정 = 방문 표시
        q.push(v);
    }
}

상태 부족. "벽을 한 번 부술 수 있다"면 (r, c)가 아니라
(r, c, 부쉈는지)가 상태입니다. 위치만 쓰면 오답.
범위 검사 순서. if (visited[nr][nc] || nr < 0) 순서로 쓰면 배열 밖을
먼저 읽어 터집니다. 범위 검사가 항상 먼저입니다.
숨바꼭질류에서 상태 공간 미제한. $\times 2$ 이동은 상한을 넘어갈 수
있으니 배열 크기(예: $2 \times 10^5$ )로 잘라야 합니다.
거리 배열 없이 깊이를 세려고 함. 레벨이 필요하면 dist 배열 또는
"현재 레벨 크기만큼 꺼내기" 패턴 중 하나를 정확히 쓰세요.

4. 연습 방법

이 페이지 오른쪽의 추천 문제는 쉬운 것부터 어려운 것 순입니다. 격자
미로 → 다중 시작점 → 상태 전이 퍼즐 순으로 상태 정의가 점점 어려워집니다.

각 문제에서 코딩 전에 "정점(상태)은 무엇이고 간선(전이)은 무엇인가"를
한 줄로 적으세요. 이 한 줄이 BFS 문제의 전부입니다. 3문제 이상 풀어
클리어하면 레이팅의 CLASS 보너스에 반영됩니다.

Practice problem 알파카컵 1회: C - 알파카의 트로피 미로 선택 25m

A00003

알파카컵 1회: C - 알파카의 트로피 미로

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Practice problem 배고픈 주몽이 선택 25m

R00007

배고픈 주몽이

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

골드 V 지금 풀기

Level 3 · Explorer

Explorer

그래프 이론 · Explorer 단계

0/30 완료

Lesson 우선순위 큐로 찾는 최단 경로 필수 8m

어떤 문제를 푸는가

가중치가 음이 아닌 방향/무방향 그래프에서, 한 시작점 $$s$$ 로부터 모든
정점까지의 최단 거리를 구합니다. 간선 가중치가 모두 1이면 BFS로 충분하지만,
가중치가 제각각이면 "가까운 칸부터 차례로"라는 BFS의 전제가 깨집니다.
다익스트라는 이 일반화를 다룹니다.

핵심 아이디어

거리 배열 dist[v]를 모두 $\infty$ 로 두고 dist[s] = 0에서 시작합니다.
아직 확정되지 않은 정점 중 dist가 가장 작은 정점 $$u$$ 를 고르고, 그
정점을 통한 이완(relaxation)을 합니다.

$\text{dist}[v] \leftarrow \min(\text{dist}[v],\ \text{dist}[u] + w(u, v))$

한 번 "가장 작은 값으로 뽑힌" 정점은 다시 갱신되지 않습니다. 이 정점을
확정(finalize) 했다고 부릅니다.

왜 옳은가 (정당성 스케치)

귀류법으로 봅니다. 어떤 정점 $$u$$ 를 확정하는 순간 dist[u]가 실제 최단 거리가
아니라고 가정합시다. 그러면 더 짧은 경로 $$P$$ 가 존재합니다. $$P$$ 를 따라가다 보면
아직 확정되지 않은 첫 정점 $$x$$ 가 있습니다. $$x$$ 의 직전 정점은 이미
확정되었으므로 dist[x]는 그 시점에 이완되어 있고, 가중치가 음이 아니므로

$\text{dist}[x] \le (\text{경로 } P \text{에서 } x \text{까지의 거리}) \le \text{dist}[u]$

가 됩니다. 그렇다면 우리는 $$u$$ 대신 $$x$$ 를 먼저 뽑았어야 하므로 모순입니다.
음이 아닌 가중치 가정이 바로 두 번째 부등식을 보장하는 열쇠입니다. 음수
간선이 있으면 이 논증이 무너지고, 그때는 벨만-포드를 써야 합니다.

자료구조와 복잡도

매번 "가장 작은 dist"를 찾는 일을 최소 힙(우선순위 큐) 으로 합니다.
각 간선은 최대 한 번 큐에 (key, 정점) 쌍을 넣으므로 큐 연산은 $$O(E)$$ 번,
각 연산이 $O(\log E) = O(\log V)$ 이므로 전체는

$O(E \log V)$

입니다. 정점 수가 적고 간선이 빽빽하면( $E \approx V^2$ ) 힙 없이 매번 선형
탐색하는 $$O(V^2)$$ 구현이 오히려 빠를 수 있습니다.

흐름 한눈에 보기

단계	하는 일
초기화	`dist[s]=0`, 나머지 $\infty$ , 큐에 `(0, s)`
추출	큐에서 거리 최소 정점 $$u$$ 를 꺼낸다
게으른 검사	꺼낸 거리가 `dist[u]`보다 크면 버린다
이완	$$u$$ 의 각 이웃 $$v$$ 에 대해 `dist`를 갱신하고 큐에 넣는다

여기서 게으른 삭제(lazy deletion) 가 중요합니다. 우선순위 큐는 임의 원소의
값을 직접 줄이기 어렵기 때문에, 갱신할 때마다 새 쌍을 그냥 넣고 꺼낼 때
"이미 더 좋은 값으로 확정된 정점"이면 무시합니다.

정리

음이 아닌 가중치 단일 시작점 최단 경로의 표준 해법.
정당성의 핵심은 "음이 아닌 가중치 → 먼저 뽑힌 정점이 최단 확정".
힙 기반 $O(E \log V)$ , 조밀 그래프는 $$O(V^2)$$ 도 고려.
다음 강의에서 실제 구현과 흔한 함정을 다룹니다.

Lesson 다익스트라 구현과 함정 선택 8m

우선순위 큐 기반 표준 구현 (C++)

거리 배열은 큰 값으로 초기화하고, 최소 힙을 만들기 위해 greater를 씁니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

int main() {
    int n, m, s;
    cin >> n >> m >> s;            // 정점 수, 간선 수, 시작점
    vector<vector<pair<int, int>>> adj(n + 1);  // (이웃, 가중치)
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});  // 무방향이면 반대 방향도 추가
    }

    vector<ll> dist(n + 1, INF);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>,
                   greater<>> pq;   // (거리, 정점) 최소 힙
    dist[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;  // 게으른 삭제: 낡은 항목은 버린다
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    for (int v = 1; v <= n; v++)
        cout << (dist[v] == INF ? -1 : dist[v]) << '\n';
}

파이썬 구현

import sys, heapq
input = sys.stdin.readline
INF = float('inf')

def dijkstra(n, adj, s):
    dist = [INF] * (n + 1)
    dist[s] = 0
    pq = [(0, s)]                    # (거리, 정점)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:             # 게으른 삭제
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

흔한 함정

거리 자료형 — 간선 가중치 합이 21억을 넘으면 int가 넘칩니다. C++은
long long, INF도 덧셈 후 넘치지 않게 1e18 정도로 잡습니다.
게으른 삭제 누락 — if (d > dist[u]) continue;를 빼면 같은 정점을 여러
번 펼쳐 사실상 $$O(VE)$$ 로 느려집니다. 정답은 나와도 시간 초과가 납니다.
음수 간선 — 단 하나라도 음수면 다익스트라는 틀립니다. 음수가 있으면
벨만-포드/SPFA로 바꾸세요.
무방향 그래프 — 양쪽 방향을 모두 인접 리스트에 넣어야 합니다.
visited 배열로 막기 — dist 비교로 충분합니다. 별도 visited를 두면
같은 효과지만, 잘못 두면 더 짧은 갱신을 막을 수 있어 주의합니다.

경로 복원

최단 거리뿐 아니라 실제 경로가 필요하면 이완할 때 직전 정점을 기록합니다.

if (dist[u] + w < dist[v]) {
    dist[v] = dist[u] + w;
    par[v] = u;            // 어디서 왔는지 기억
    pq.push({dist[v], v});
}
// 복원: t에서 par를 따라 s까지 올라가 뒤집는다

응용 패턴

K번째 최단 경로 / 특정 정점 경유 — 상태에 추가 정보를 붙여 정점을 확장.
0-1 BFS — 가중치가 0과 1뿐이면 덱으로 $$O(V+E)$$ .
간선이 조건부 — "기름통 용량" 같은 제약을 정점에 곱해 상태 그래프를 만든 뒤
다익스트라. 즉 "현재 상태"를 정점으로 보는 모델링이 핵심입니다.

거리가 단조 증가한다는 성질(음이 아닌 가중치) 위에서 작동한다는 점만 늘
의식하면 변형 문제도 어렵지 않게 적용할 수 있습니다.

Lesson 실전 가이드 — 최단 경로 문제 판별과 스킵 조건 선택 8m

출제 신호

다음 조합이 보이면 다익스트라가 1순위 후보입니다.

"한 정점에서 다른 정점(들)까지의 최단 거리/최소 비용"
간선 가중치가 모두 음이 아님 (1 이상, 0 이상 등) — 문제에 명시되거나
비용의 의미상(시간, 요금, 거리) 음수가 불가능한 경우
$V \le 10^5$ , $E \le 3 \times 10^5$ 규모 — $O(E \log V)$ 를 요구하는 전형적 크기

반대 신호도 같이 외워 두세요. 가중치가 전부 1이면 그냥 BFS,
0과 1뿐이면 0-1 BFS, 음수 간선이 있으면 벨만-포드,
모든 쌍이 필요하고 $V \le 500$ 이면 플로이드-워셜입니다.
"경유지 제약", "도로를 $$k$$ 개까지 공짜로" 같은 조건은 정점을
(위치, 사용한 혜택 수)로 확장한 상태 그래프 다익스트라의 신호입니다.

풀이 결정 절차

시작점이 하나인가? (여러 개면 가상 시작점 또는 멀티 소스로 초기 큐에 전부 투입)
음수 간선이 없는가? — 없다는 근거를 제약에서 직접 확인합니다.
$E \log V$ 를 계산해 시간 안에 드는지 검산합니다. $E \approx V^2$ 의 조밀
그래프면 힙 없는 $$O(V^2)$$ 구현이 더 빠를 수 있습니다.
거리의 최대값을 추정합니다 — $V \times w_{\max}$ 가 int 범위를 넘으면 long long.
상태 확장이 필요한지(남은 연료, 사용한 쿠폰 수 등) 판단하고, 필요하면
dist[v][상태] 2차원으로 키웁니다.

자주 하는 실수

가장 흔한 버그는 게으른 삭제 스킵 조건 누락입니다. 같은 정점이 낡은
거리로 큐에 여러 번 들어 있는데 전부 처리하면 최악에 시간 초과가 납니다.

while pq:
    d, u = heapq.heappop(pq)
    if d > dist[u]:      # 이 한 줄이 없으면 낡은 항목을 전부 확장 → TLE
        continue
    ...

visited 배열로 처리한다면 꺼낼 때(pop) 확정해야 합니다. 큐에 넣을 때
방문 표시를 하면 더 짧은 경로로의 갱신이 막혀 오답이 됩니다 — 이건 BFS의
습관이 그대로 옮아온 전형적인 버그입니다.

// 잘못: push 시점에 방문 처리 (가중치 그래프에서 오답)
if (!visited[v]) { visited[v] = true; pq.push({nd, v}); }

// 올바름: pop 시점에 확정
auto [d, u] = pq.top(); pq.pop();
if (visited[u]) continue;
visited[u] = true;

거리 오버플로 — 간선 가중치 $$10^9$$ $\times$ 경로 길이면 int가 터집니다.
dist는 long long, INF는 1e18 수준으로.
최소 힙 설정 실수 — C++ priority_queue는 기본이 최대 힙입니다.
greater<>를 빼먹으면 가장 먼 정점부터 확정해 오답이 납니다.
무방향 간선을 한쪽만 추가 — 입력이 양방향 도로인지 꼭 확인하세요.

연습 방법

사이드바 연습 목록의 기본 최단 경로 문제로 표준 구현을 한 번 "보지 않고"
써 보세요. 그다음 경로 복원(직전 정점 기록), 상태 확장형(예: 간선 $$k$$ 개
무료) 순서로 난도를 올립니다. 제출 전 자가 점검 세 가지 — 스킵 조건,
long long, 최소 힙 — 를 루틴으로 만들면 다익스트라에서 틀릴 일이 거의
없어집니다. 태그된 문제 3문제 이상 해결 시 마스터 처리되어 레이팅의
CLASS 보너스에 반영됩니다.

Practice problem 외곽 순환 도로 선택 25m

KOI00058

외곽 순환 도로

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Practice problem 드론 배달망 선택 25m

R01401

드론 배달망

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Lesson 덱 하나로 끝내는 0/1 최단 경로 필수 8m

문제 상황

간선 가중치가 0 또는 1뿐인 그래프에서 최단 경로를 구해야 한다고 합시다.
다익스트라( $O(E \log V)$ )도 답을 주지만, 이 특수한 구조에서는 우선순위 큐가
과한 도구입니다. 덱(deque) 하나면 $$O(V+E)$$ 에 끝납니다.

핵심 아이디어

BFS가 옳은 이유를 떠올려 보면 — 큐 안의 정점들이 항상 거리 순으로
정렬되어 있기 때문입니다. 가중치가 0/1이면 이 성질을 덱으로 유지할 수 있습니다.

가중치 0인 간선으로 이완하면, 거리가 같으므로 덱의 앞에 넣는다.
가중치 1인 간선으로 이완하면, 거리가 1 크므로 덱의 뒤에 넣는다.

이렇게 하면 덱 안의 거리값이 항상 단조(차이가 최대 1)로 유지되어, 앞에서
꺼내는 순서가 다익스트라의 추출 순서와 같아집니다.

왜 옳은가 (스케치)

덱 안의 원소들의 거리는 항상 $$d$$ 또는 $$d+1$$ 두 값뿐임을 귀납적으로 보일 수
있습니다. 앞에서 꺼낸 정점의 거리가 최소이므로, 다익스트라와 같은 논리로
확정(finalize)해도 안전합니다.

복잡도

각 정점·간선이 상수 번만 처리되므로 $$O(V+E)$$ . 다익스트라보다 로그 인자가
빠지고, 상수도 가볍습니다.

전형적인 등장 형태

미로에서 "벽 부수기 최소 횟수" — 이동은 0, 벽 부수기는 1.
레이저/거울 회전 문제 — 직진은 0, 방향 전환은 1.
"최소 횟수의 특수 행동"을 묻는 격자 문제 전반.

가중치가 0과 1만 있는지 먼저 확인하세요. 0/1이 아니라 작은 정수 $$k$$ 까지면
다이얼(Dial's) 알고리즘이라는 일반화도 있습니다.

Lesson 0-1 BFS 구현과 함정 선택 8m

참조 구현 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;  // 정점, 간선 수
    cin >> n >> m;
    vector<vector<pair<int,int>>> adj(n + 1);  // (다음 정점, 가중치 0/1)
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    const int INF = 1e9;
    vector<int> dist(n + 1, INF);
    deque<int> dq;
    dist[1] = 0;
    dq.push_back(1);
    while (!dq.empty()) {
        int u = dq.front(); dq.pop_front();
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);  // 같은 거리 → 앞
                else        dq.push_back(v);   // +1 거리 → 뒤
            }
        }
    }
    cout << dist[n] << '\n';
}

참조 구현 (Python)

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, w = map(int, input().split())
    adj[u].append((v, w))
    adj[v].append((u, w))

INF = float('inf')
dist = [INF] * (n + 1)
dist[1] = 0
dq = deque([1])
while dq:
    u = dq.popleft()
    for v, w in adj[u]:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            if w == 0:
                dq.appendleft(v)  # 가중치 0 → 앞에
            else:
                dq.append(v)      # 가중치 1 → 뒤에
ans = dist[n]
print(ans)

자주 하는 실수

방문 체크를 큐에 넣을 때 하는 것 — 0-1 BFS에서는 같은 정점이 여러 번
덱에 들어갈 수 있습니다. dist 갱신 조건(dist[u]+w < dist[v])으로만
걸러야 안전합니다. 꺼낼 때 더 좋은 기록이 이미 있으면 건너뛰는 가드를
추가해도 됩니다.
격자 문제에서 상태 확장 누락 — "벽을 k번까지 부술 수 있다"류는
(행, 열, 부순 횟수)가 상태입니다. 정점 수가 늘어난 만큼 dist 배열도 함께.
BFS처럼 push할 때 거리를 확정하면 안 됩니다 — 0 간선 때문에 같은 거리의
더 짧은 경로가 뒤늦게 발견될 수 있습니다.

연습 포인트

벽 부수고 이동하기류 문제에서 (이동=0/부수기=1)으로 모델링하는 연습,
그리고 같은 문제를 다익스트라로도 풀어 시간 차이를 비교해 보세요.

Lesson 실전 가이드 — 가중치 0/1 그래프 알아보기 선택 8m

출제 신호

0-1 BFS는 문제가 "0-1 BFS를 쓰라"고 말해 주지 않습니다. 가중치가 0 아니면
1뿐인 그래프를 스스로 모델링해야 보입니다. 전형적인 신호는 이렇습니다.

"벽을 최소 몇 개 부수고 도착할 수 있는가" — 빈 칸 이동은 0, 벽 부수기는 1
"방향을 최소 몇 번 바꾸는가" — 같은 방향 직진은 0, 회전은 1
"순간이동은 공짜, 걷기는 1초" 류의 두 종류 이동
"규칙을 최소 몇 번 어기는가", "다리를 최소 몇 개 놓는가"

즉 "비용이 드는 행동의 횟수를 최소화"하고 나머지 이동이 공짜라면,
정점 수가 $$10^6$$ 격자급이어도 $$O(V + E)$$ 로 풉니다. 가중치 종류가 0/1 두
가지라는 점만 확인되면 다익스트라보다 로그 인자 하나가 빠집니다.

풀이 결정 절차

이동(전이)을 전부 나열하고 각각의 비용이 0 또는 1로만 떨어지는지 확인합니다.
(0/1이 아니라 0/½ 이상 섞이면 그냥 다익스트라로 갑니다.)
상태를 정의합니다 — 격자라면 (행, 열), 회전 문제라면 (행, 열, 방향)처럼
비용 판정에 필요한 정보를 상태에 포함해야 합니다.
덱(deque)을 준비합니다 — 비용 0 전이는 앞에, 비용 1 전이는 뒤에 넣습니다.
복잡도 검산 — 상태 수 $\times$ 전이 수가 $$10^7$$ 안쪽인지 확인합니다.

핵심 불변식은 "덱 안의 거리값은 항상 단조(차이가 최대 1)"라는 것입니다.
그래서 다익스트라처럼 힙이 없어도 꺼내는 순서가 거리 오름차순이 됩니다.

자주 하는 실수

넣을 때 방문 확정 — 가중치 1짜리 BFS 습관대로 enqueue 시점에 방문
처리하면, 나중에 비용 0 경로로 더 싸게 도달할 수 있는 상태가 막힙니다.
거리 비교로 갱신하고, 꺼낼 때 낡은 항목을 버리는 게 안전합니다.

from collections import deque

dist = [[INF] * m for _ in range(n)]
dist[sy][sx] = 0
dq = deque([(sy, sx)])
while dq:
    y, x = dq.popleft()
    for ny, nx, w in transitions(y, x):     # w 는 0 또는 1
        if dist[y][x] + w < dist[ny][nx]:
            dist[ny][nx] = dist[y][x] + w
            if w == 0:
                dq.appendleft((ny, nx))     # 0 은 앞으로
            else:
                dq.append((ny, nx))         # 1 은 뒤로

0 전이를 뒤에 넣음 — appendleft/push_front를 빼먹으면 그냥 틀린
BFS가 됩니다. 0과 1의 행선지(앞/뒤)를 제출 전에 꼭 확인하세요.
상태 부족 — "방향 전환 최소화"에서 (행, 열)만 들고 가면 같은 칸을
다른 방향으로 지나는 경우를 구분하지 못해 오답입니다. (행, 열, 방향)으로 확장.
다익스트라로 풀어도 되는데 시간이 빠듯한 경우 — $$10^6$$ 상태 $\times$
$\log$ 가 아슬아슬하면 0-1 BFS로 바꾸는 것 자체가 정해인 문제도 있습니다.

연습 방법

사이드바 연습 목록에서 "벽 부수기" 류의 격자 문제부터 시작해, 상태에
방향이 들어가는 회전 문제로 올라가세요. 문제를 읽을 때 "공짜 행동 / 1짜리
행동"을 표로 적어 보고, 그래프 모델링이 끝난 뒤에야 코드를 시작하는 습관이
중요합니다. 같은 문제를 다익스트라로도 한 번 풀어 두 구현의 차이(힙 vs 덱)를
비교해 보면 이해가 굳어집니다. 태그된 문제 3문제 이상 해결 시 마스터
처리되어 레이팅 CLASS 보너스에 반영됩니다.

Practice problem 알파카컵 1회: C - 알파카의 트로피 미로 선택 25m

A00003

알파카컵 1회: C - 알파카의 트로피 미로

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Practice problem 배고픈 주몽이 선택 25m

R00007

배고픈 주몽이

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

골드 V 지금 풀기

Lesson MST와 컷 성질 필수 8m

어떤 문제를 푸는가

가중치 무방향 연결 그래프에서, 모든 정점을 연결하면서 간선 가중치 합이 최소
인 트리를 찾습니다. 도시들을 가장 싸게 도로로 잇기, 네트워크 최소 비용 연결
등이 전형적인 예입니다. 정점이 $$V$$ 개면 트리는 정확히 $$V-1$$ 개의 간선을 갖습니다.

두 가지 핵심 성질

MST 알고리즘의 정당성은 두 성질에서 나옵니다.

컷 성질 (Cut Property)

정점을 두 그룹으로 나눈 임의의 컷 에서, 그 컷을 가로지르는 간선 중 가장
가벼운 간선 은 어떤 MST에 반드시 포함됩니다.

직관: 그 가벼운 간선을 MST가 안 쓴다면, 컷을 가로지르는 다른(더 무거운)
간선을 쓰고 있어야 합니다. 그 무거운 간선을 빼고 가벼운 간선으로 바꾸면 여전히
트리이면서 비용이 줄어드니, 원래 것이 최소가 아니었다는 모순입니다.

사이클 성질 (Cycle Property)

어떤 사이클에서 가장 무거운 간선 은 어떤 MST에도 포함되지 않습니다.

이 두 성질이 그리디(가벼운 간선부터 채택)가 옳음을 보장합니다.

두 가지 표준 알고리즘

	크루스칼	프림
관점	간선 중심	정점 중심
자료구조	정렬 + 유니온 파인드	우선순위 큐
진행	가벼운 간선부터, 사이클 안 만들면 채택	트리에 가장 가까운 정점을 흡수
복잡도	$O(E \log E)$	$O(E \log V)$
유리한 경우	희소 그래프	조밀 그래프

크루스칼의 아이디어

간선을 가중치 오름차순으로 정렬하고, 가벼운 것부터 본다. 그 간선의 두 끝점이
아직 다른 그룹 이면(유니온 파인드로 확인) 채택하고 합친다. 같은 그룹이면
추가 시 사이클이 생기므로 버린다. 이는 컷 성질의 직접적 적용입니다.

프림의 아이디어

한 정점에서 시작해 트리를 키운다. 매번 트리와 트리 밖을 잇는 가장 가벼운
간선 을 골라 새 정점을 흡수한다(우선순위 큐로 관리). 다익스트라와 형제처럼
닮았지만, 거리가 아니라 "트리까지의 간선 가중치"를 기준으로 삼습니다.

복잡도 정리

크루스칼: 정렬 $O(E \log E)$ 가 지배. DSU는 거의 상수.
프림(힙): $O(E \log V)$ .

대부분의 경우 구현이 단순한 크루스칼을 기본으로 씁니다. 다음 강의에서 두
구현과 응용을 봅니다.

Lesson 크루스칼·프림 구현 선택 8m

크루스칼 구현 (C++)

유니온 파인드와 결합합니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct DSU {
    vector<int> p, s;
    DSU(int n) : p(n), s(n, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { while (p[x] != x) x = p[x] = p[p[x]]; return x; }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (s[a] < s[b]) swap(a, b);
        p[b] = a; s[a] += s[b];
        return true;
    }
};

int main() {
    int n, m; cin >> n >> m;
    vector<array<ll, 3>> e(m);            // {가중치, u, v}
    for (auto& x : e) cin >> x[1] >> x[2] >> x[0];
    sort(e.begin(), e.end());             // 가중치 오름차순

    DSU dsu(n + 1);
    ll cost = 0; int cnt = 0;
    for (auto& [w, u, v] : e) {
        if (dsu.unite(u, v)) {            // 사이클 안 생기면 채택
            cost += w;
            if (++cnt == n - 1) break;    // 간선 V-1개면 완성
        }
    }
    cout << (cnt == n - 1 ? cost : -1) << '\n';  // 연결 불가면 -1
}

cnt == n - 1로 끝나면 MST 완성, 못 채우면 그래프가 연결되지 않은 것입니다.

프림 구현 (C++, 힙)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n, m; cin >> n >> m;
    vector<vector<pair<int, ll>>> adj(n + 1);   // (이웃, 가중치)
    for (int i = 0; i < m; i++) {
        int u, v; ll w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});               // 무방향
    }

    vector<char> in(n + 1, 0);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    pq.push({0, 1});                            // 정점 1에서 시작
    ll cost = 0; int cnt = 0;
    while (!pq.empty()) {
        auto [w, u] = pq.top(); pq.pop();
        if (in[u]) continue;                    // 이미 트리에 있음
        in[u] = 1; cost += w; cnt++;
        for (auto [v, ww] : adj[u])
            if (!in[v]) pq.push({ww, v});
    }
    cout << (cnt == n ? cost : -1) << '\n';
}

다익스트라와 코드가 거의 같지만, 큐에 넣는 값이 "시작점까지의 누적 거리"가
아니라 "이 간선 하나의 가중치"라는 점만 다릅니다.

흔한 함정

무방향 간선 양방향 등록 — 프림에서 양쪽을 다 넣어야 합니다.
연결성 미확인 — 채택한 간선이 $$V-1$$ 개가 안 되면 MST가 없습니다(비연결).
정렬 키 — 크루스칼에서 가중치를 맨 앞에 두어 가중치 기준 정렬.
long long — 가중치 합이 클 수 있습니다.

응용 패턴

두 번째로 작은 신장 트리 — MST의 각 간선을 하나씩 제외하고 재계산하거나,
사이클 성질을 이용.
최소 병목 신장 트리 — 가장 무거운 간선을 최소화 → MST가 그 답을 줍니다.
부분 연결만 필요(슈타이너 비슷) — 일부 정점만 잇기는 일반적으로 어렵지만,
특수 케이스는 MST 변형으로.
오프라인 "어떤 가중치 이하 간선만 쓰면 연결되나" — 크루스칼 진행을 그대로
활용(크루스칼 재구성 트리로 확장).

컷 성질이라는 단단한 토대 위에서 "가벼운 간선부터"라는 그리디가 통한다는 점이
이 단원의 핵심입니다.

Lesson 실전 가이드 — MST 출제 패턴과 크루스칼 점검표 선택 8m

출제 신호

MST는 문구가 비교적 정직한 편입니다.

"모든 도시(컴퓨터, 섬)를 연결하는 최소 비용" — 가장 전형적인 문장
"전선/도로/다리를 깔되 총 비용을 최소로", "유지할 간선만 남기고 나머지는 철거"
살짝 변장한 형태: "비용이 가장 비싼 간선을 최소화하며 연결"
(MST의 간선 최댓값이 답 — MST는 최소 병목 신장 트리이기도 합니다)
정점이 좌표로 주어지고 "거리 비용으로 모두 연결" — 간선을 직접 만들어야 하는 형태

규모 신호는 $E \le 10^5{\sim}10^6$ 에 정렬 $O(E \log E)$ 가 통하는 크기입니다.
좌표 $$N$$ 개로 완전 그래프를 만들면 간선이 $$N^2/2$$ 개가 되니, $N \le 2000$
정도까지만 완전 그래프가 가능하다는 것도 같이 기억해 두세요.

풀이 결정 절차

"전부 연결 + 비용 최소"인지 확인합니다. 특정 두 점만 이으면 최단 경로 문제입니다.
간선 리스트가 주어지는가, 직접 생성해야 하는가(좌표 거리 등)를 판단합니다.
크루스칼(간선 정렬 + 유니온 파인드)을 기본으로 잡습니다. 조밀 그래프
( $E \approx V^2$ )면 프림 $$O(V^2)$$ 가 메모리·시간에서 유리할 수 있습니다.
연결이 보장되는지 확인합니다 — 보장이 없으면 "불가능" 출력 분기가 필요합니다.
비용 합의 최대값을 추정해 long long 여부를 정합니다.

자주 하는 실수

간선 수 검증 누락 — 크루스칼이 끝났을 때 채택한 간선이 $$V-1$$ 개가 아니면
그래프가 애초에 연결돼 있지 않은 것입니다. 합만 출력하면 오답.

sort(edges.begin(), edges.end());          // (w, u, v) 가중치순
long long total = 0; int used = 0;
for (auto [w, u, v] : edges) {
    if (find(u) == find(v)) continue;      // 사이클 — 버린다
    unite(u, v);
    total += w; used++;
}
if (used != n - 1) cout << -1 << '\n';     // 연결 불가 판정을 잊지 말 것
else cout << total << '\n';

유니온 파인드 최적화 누락 — 경로 압축 없는 DSU로 $$10^6$$ 간선을 돌리면
정렬보다 DSU에서 시간이 터집니다.
비용 합 오버플로 — 간선 $$10^5$$ 개 $\times$ 가중치 $$10^6$$ 이면 이미 int 초과.
"최대 비용 간선 최소화" 문제에서 합을 출력 — 병목 변형은 답이 합이 아니라
채택한 간선 중 최댓값입니다. 문제의 목적 함수를 다시 읽으세요.
프림에서 다익스트라 습관 — 프림의 키는 "시작점부터의 거리"가 아니라
"트리까지의 간선 한 개 비용"입니다. dist[v] = w 갱신을
dist[v] = dist[u] + w로 쓰면 MST가 아니라 최단 경로 트리가 됩니다.

연습 방법

사이드바 연습 목록의 표준 MST 문제로 크루스칼 + DSU 템플릿을 굳히고,
이어서 (1) 좌표에서 간선을 생성하는 문제, (2) 병목(최댓값 최소화) 변형,
(3) "이미 깔린 간선이 일부 있는" 변형(해당 간선을 비용 0으로 먼저 union)
순서로 푸세요. 제출 전 점검 — 간선 $$V-1$$ 개 확인, long long, DSU 압축 —
세 줄 루틴이면 충분합니다. 태그된 문제 3문제 이상 해결 시 마스터 처리되어
레이팅 CLASS 보너스에 반영됩니다.

Practice problem 최소 신장 트리 선택 25m

R02023

최소 신장 트리

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Practice problem 가장 덜 가파른 등산로 선택 25m

R00198

가장 덜 가파른 등산로

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Lesson 음수 간선과 이완의 반복 필수 8m

어떤 문제를 푸는가

다익스트라는 음수 간선 이 있으면 틀립니다. 벨만-포드는 음수 가중치 간선이
있어도 단일 시작점 최단 경로를 구하고, 나아가 음수 사이클 의 존재까지
탐지합니다.

핵심 아이디어 — 모든 간선을 V−1번 이완

최단 경로는 사이클을 포함하지 않으므로 간선을 최대 $$V-1$$ 개 거칩니다.
따라서 모든 간선에 대한 이완을 $$V-1$$ 번 반복하면 모든 최단 거리가 확정됩니다.

$\text{매 라운드: 모든 } (u, v, w)\text{에 대해 } dist[v] \leftarrow \min(dist[v],\ dist[u] + w)$

왜 V−1번이면 충분한가

귀납적으로 봅니다. $$k$$ 번째 라운드가 끝나면, 간선을 최대 $$k$$ 개 쓰는 모든
최단 경로가 dist에 반영됩니다. 시작점에서 임의 정점까지의 최단 경로가
간선을 $\ell$ 개 쓴다면, $\ell$ 번째 라운드에 그 거리가 확정됩니다. 단순 경로의
간선 수는 최대 $$V-1$$ 이므로 $$V-1$$ 번이면 모두 끝납니다.

핵심은 라운드 안에서 모든 간선을 빠짐없이 본다는 점입니다. 순서는 상관없고,
한 라운드에서 운 좋게 더 멀리 갱신될 수도 있지만 최악의 경우를 $$V-1$$ 로 잡습니다.

음수 사이클 탐지

$$V-1$$ 번 이완 뒤에도 여전히 갱신되는 간선 이 있다면, 그 경로는 사이클로
무한히 줄어드는 음수 사이클을 포함합니다. $$V$$ 번째 라운드에서 한 번 더 돌려
갱신 여부를 확인하면 됩니다.

음수 사이클이 있으면 "최단 경로"는 $-\infty$ 로 정의되지 않으므로, 보통은
"음수 사이클 존재"만 보고합니다.

복잡도

항목	값
시간	$O(V \cdot E)$
공간	$$O(V)$$ (거리 배열)

다익스트라의 $O(E \log V)$ 보다 느립니다. 그러니 음수 간선이 없으면
다익스트라, 음수가 있거나 음수 사이클 판정이 필요하면 벨만-포드를 씁니다.

다익스트라와의 비교

	다익스트라	벨만-포드
음수 간선	불가	가능
음수 사이클	—	탐지 가능
시간	$O(E \log V)$	$$O(VE)$$
방식	최솟값 확정	전 간선 반복 이완

다음 강의에서 구현, 음수 사이클 보고, 그리고 큐로 가속하는 SPFA를 봅니다.

Lesson 벨만-포드 구현과 음수 사이클 선택 8m

표준 구현 (C++)

간선 리스트만 있으면 됩니다. 인접 리스트도 필요 없습니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

struct Edge { int u, v; ll w; };

int main() {
    int n, m; cin >> n >> m;
    vector<Edge> edges(m);
    for (auto& e : edges) cin >> e.u >> e.v >> e.w;

    vector<ll> dist(n + 1, INF);
    dist[1] = 0;                          // 시작점 1

    bool negcycle = false;
    for (int i = 1; i <= n; i++) {        // n번째에서 사이클 탐지
        for (auto& e : edges) {
            if (dist[e.u] == INF) continue;        // 도달 못한 정점은 건너뛴다
            if (dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
                if (i == n) negcycle = true;       // V번째에도 갱신 → 음수 사이클
            }
        }
    }

    if (negcycle) { cout << -1 << '\n'; return 0; }
    for (int v = 2; v <= n; v++)
        cout << (dist[v] == INF ? -1 : dist[v]) << '\n';
}

핵심 두 줄:

if (dist[e.u] == INF) continue; — 도달 못한 정점에서의 이완 금지.
이걸 빼면 INF + (음수)가 더 작아져 엉뚱한 정점이 음수로 갱신됩니다.
if (i == n) — $$V-1$$ 라운드까지가 본 계산, $$V$$ 번째 라운드의 갱신은
음수 사이클 신호입니다.

특정 시작점에서 도달 가능한 음수 사이클만

문제에 따라 "시작점에서 갈 수 있는 음수 사이클"만 의미가 있습니다. 그러면
시작점에서 도달 가능한 정점만 고려하거나, $$V$$ 번째 갱신된 정점에서 역방향
BFS로 시작점에 영향을 주는지 확인합니다.

SPFA — 큐로 가속한 벨만-포드

매 라운드 모든 간선을 보는 대신, 거리가 바뀐 정점만 큐에 넣어 그 이웃을
이완합니다. 평균적으로 빠르지만 최악은 여전히 $$O(VE)$$ 입니다.

queue<int> q;
vector<int> inq(n + 1, 0), cnt(n + 1, 0);
dist[s] = 0; q.push(s); inq[s] = 1;
while (!q.empty()) {
    int u = q.front(); q.pop(); inq[u] = 0;
    for (auto [v, w] : adj[u]) {
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            if (++cnt[v] >= n) { /* 음수 사이클 */ }
            if (!inq[v]) { q.push(v); inq[v] = 1; }
        }
    }
}

cnt[v] >= n(어떤 정점이 $$n$$ 번 이상 큐에 들어감)이면 음수 사이클입니다.

흔한 함정

도달 불가 정점 이완 — 위에서 강조한 INF 체크 누락. 가장 자주 틀립니다.
INF 덧셈 오버플로 — INF를 INT_MAX로 잡고 음수를 더하면 넘칩니다.
long long과 넉넉한 INF(1e18)를 쓰되, 도달 불가는 더하지 않기.
무방향 음수 간선 — 무방향 그래프에서 음수 간선은 곧 음수 사이클입니다.

응용 패턴

시간/환율 차익(arbitrage) — 곱셈을 로그로 바꿔 합으로, 음수 사이클 = 차익.
차분 제약 시스템 — $x_j - x_i \le c$ 형태의 부등식들을 간선으로 보고
벨만-포드로 해의 존재성(음수 사이클 = 무해)과 한 해를 구합니다.

음수가 끼어들면 다익스트라의 "한 번 확정"이 무너진다는 점, 그래서 "모든 간선을
반복해서 이완"으로 돌아간다는 점이 이 단원의 본질입니다.

Lesson 실전 가이드 — 음수 간선 신호와 INF 전파 차단 선택 8m

출제 신호

벨만-포드를 골라야 하는 순간은 명확합니다.

최단 경로 문제인데 간선 가중치가 음수일 수 있음 — "시간이 줄어드는
웜홀", "비용이 환급되는 경로" 같은 서사가 단서입니다.
"음수 사이클(시간 역행, 무한히 이득)이 존재하는지 판정하라"
제약 신호: $V \le 500$ , $E \le 6000$ 정도의 작은 그래프 — $$O(VE)$$ 가
허용되는 크기라는 뜻 자체가 벨만-포드 신호입니다.
변형 신호: "간선을 정확히/최대 $$k$$ 개만 써서 최단 경로" — 이완 횟수를
제한하는 벨만-포드 변형(라운드별 스냅숏)입니다.

음수 간선이 없다면 같은 문제를 다익스트라로 더 빠르게 풉니다. 벨만-포드는
"음수 간선 또는 이완 횟수 제한"이라는 조건이 있을 때만 꺼내는 도구입니다.

풀이 결정 절차

음수 간선 유무를 제약에서 확인합니다. 있다면 다익스트라는 탈락.
$V \times E$ 를 계산해 $$10^8$$ 안쪽인지 검산합니다.
문제가 묻는 것을 구분합니다 — (a) 최단 거리, (b) 음수 사이클 존재 여부,
© 음수 사이클의 영향을 받는 정점 판별. ©는 $$V$$ 번째 라운드에서
갱신된 정점으로부터 도달 가능한 모든 정점을 추가로 퍼뜨려야 합니다.
거리 자료형 — 음수 누적까지 고려해 long long이 기본입니다.

자주 하는 실수

가장 치명적인 버그는 INF 정점에서의 이완입니다. 아직 도달하지 못한
정점( $\text{dist}=\infty$ )에서 음수 간선을 이완하면 $\infty + (-w)$ 라는
가짜 거리가 전파되고, C++에선 오버플로로 음수가 되어 그래프 전체가 오염됩니다.

for (int round = 0; round < n - 1; round++)
    for (auto [u, v, w] : edges) {
        if (dist[u] == INF) continue;      // 이 줄이 없으면 INF-오염 + 오버플로
        dist[v] = min(dist[v], dist[u] + w);
    }

사이클 판정 라운드 누락 — $$V-1$$ 라운드로 거리는 수렴하지만, 음수 사이클
판정은 한 라운드 더( $$V$$ 번째) 돌려서 여전히 갱신되는지 봐야 합니다.
"시작점에서 도달 가능한" 사이클만 인정해야 하는 문제 — 그래프 어딘가의
음수 사이클과 시작점에서 닿는 음수 사이클은 다릅니다. 도달 불가 정점에서의
갱신을 사이클로 오인하지 않도록 위의 INF continue가 여기서도 핵심입니다.
조기 종료 최적화의 오해 — 한 라운드 동안 갱신이 전혀 없으면 즉시 끝내도
됩니다. 이 플래그를 음수 사이클 판정과 혼동해 거꾸로 쓰는 실수가 있습니다.

for r in range(n):                       # n 라운드: 마지막 라운드는 판정용
    updated = False
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            updated = True
            if r == n - 1:               # V번째 라운드에도 갱신 → 음수 사이클
                has_negative_cycle = True
    if not updated:
        break

연습 방법

사이드바 연습 목록의 기본 음수 간선 최단 경로(웜홀류)로 표준 구현과 사이클
판정을 익히고, "도달 가능한 사이클만" 따지는 변형, 간선 개수 제한 변형 순서로
확장하세요. 매 문제에서 "INF 스킵을 넣었는가, $$V$$ 번째 라운드를 돌렸는가,
long long인가"를 점검하면 벨만-포드 오답의 90%는 사라집니다. 태그된 문제
3문제 이상 해결 시 마스터 처리되어 레이팅 CLASS 보너스에 반영됩니다.

Practice problem 환차익 거래 탐지 선택 25m

R00210

환차익 거래 탐지

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Practice problem 웜홀 여행 선택 25m

R00209

웜홀 여행

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Lesson 모든 쌍 최단 경로의 DP 필수 8m

어떤 문제를 푸는가

모든 정점 쌍 $$(i, j)$$ 사이의 최단 거리를 한꺼번에 구합니다. 정점이 적고
( $V \le 400$ 정도) 쌍 전부의 거리가 필요할 때, 한 줄짜리 삼중 루프로 끝나는
이 방법이 압도적으로 편합니다. 음수 간선도 허용합니다(음수 사이클만 없으면).

핵심 아이디어 — 경유 정점을 하나씩 허용

dist[i][j]를 "정점 $$i$$ 에서 $$j$$ 로 가는 최단 거리"로 두고, 경유해도 되는
중간 정점의 집합을 $\{1\}, \{1,2\}, \dots$ 처럼 점점 넓혀 갑니다.

$$k$$ 번째 정점까지 경유를 허용했을 때의 거리를 $$dist_k[i][j]$$ 라 하면,

$dist_k[i][j] = \min\bigl(dist_{k-1}[i][j],\ dist_{k-1}[i][k] + dist_{k-1}[k][j]\bigr)$

즉 " $$k$$ 를 거치지 않는 기존 경로" vs " $i \to k \to j$ 로 $$k$$ 를 거치는 경로"
중 작은 쪽입니다.

왜 옳은가

$$i$$ 에서 $$j$$ 로 가는 임의의 최단 경로를 봅니다. 그 경로가 사용하는 중간 정점들
중 번호가 가장 큰 것 을 $$k$$ 라 하면, 경로는 " $i \to k$ (중간 정점 번호 모두
$$)" + "\(k \to j$ (역시 모두 $)"로 쪼개집니다. 두 조각은 정확히 \(dist_{k-1}$가 다루는 경우이므로, $k$를 마지막으로 허용하는 단계에서 이 경로가 포착됩니다. 모든 $k$를 차례로 허용하면 모든 최단 경로가 고려됩니다.$

여기서 $$k$$ 루프가 가장 바깥 이어야 한다는 점이 절대적으로 중요합니다.

1차원으로 in-place 갱신해도 되는 이유

$$k$$ 단계에서 dist[i][k]와 dist[k][j]는 이번 단계에 갱신되더라도 값이
변하지 않습니다 (dist[k][k] = 0이므로). 그래서 배열 한 장으로 덮어써도
정확합니다.

복잡도

항목	값
시간	$$O(V^3)$$
공간	$$O(V^2)$$

$$V = 400$$ 이면 $6.4 \times 10^7$ 로 충분히 빠릅니다. $$V$$ 가 수천을 넘으면
못 씁니다 — 그때는 각 정점마다 다익스트라( $O(V \cdot E \log V)$ )를 고려합니다.

음수 사이클 탐지

플로이드-워셜 후 어떤 정점 $$i$$ 에 대해 dist[i][i] < 0이면, $$i$$ 가 음수
사이클 위에 있다는 뜻입니다. 자기 자신으로 돌아오는 비용이 음수일 수 없기
때문입니다. 다음 강의에서 구현과 응용을 봅니다.

Lesson 플로이드-워셜 구현과 활용 선택 8m

표준 구현 (C++)

루프 순서 k, i, j 를 절대 어기지 마세요.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

int main() {
    int n, m; cin >> n >> m;
    vector<vector<ll>> dist(n + 1, vector<ll>(n + 1, INF));
    for (int i = 1; i <= n; i++) dist[i][i] = 0;   // 자기 자신은 0

    for (int e = 0; e < m; e++) {
        int u, v; ll w; cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], w);            // 중복 간선은 최솟값
    }

    for (int k = 1; k <= n; k++)                     // 경유 정점이 바깥
        for (int i = 1; i <= n; i++) {
            if (dist[i][k] == INF) continue;        // 가지치기 + 오버플로 방지
            for (int j = 1; j <= n; j++)
                if (dist[k][j] != INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cout << (dist[i][j] == INF ? -1 : dist[i][j]) << ' ';
        cout << '\n';
    }
}

if (dist[i][k] == INF) continue;는 도달 불가 정점을 통한 잘못된 갱신을
막고, 안쪽 루프도 통째로 건너뛰어 상수배 속도까지 챙깁니다.

파이썬 구현

import sys
input = sys.stdin.readline
INF = float('inf')

n, m = map(int, input().split())
dist = [[INF] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    dist[i][i] = 0
for _ in range(m):
    u, v, w = map(int, input().split())
    dist[u][v] = min(dist[u][v], w)

for k in range(1, n + 1):
    dk = dist[k]
    for i in range(1, n + 1):
        dik = dist[i][k]
        if dik == INF:
            continue
        di = dist[i]
        for j in range(1, n + 1):
            nd = dik + dk[j]
            if nd < di[j]:
                di[j] = nd

파이썬 $$O(V^3)$$ 는 상수가 커서 $$V$$ 가 수백이면 위처럼 지역 변수로 캐싱해
가속해야 시간 안에 듭니다.

흔한 함정

루프 순서 — i, j, k나 i, k, j로 잘못 짜면 틀린 답이 나옵니다.
반드시 k가 가장 바깥. 이 단원에서 단연 1순위 실수입니다.
INF 덧셈 오버플로 — 도달 불가를 더하지 않도록 위처럼 검사.
자기 루프 초기화 — dist[i][i] = 0을 잊으면 안 됩니다.
중복 간선 — 같은 $$(u, v)$$ 가 여러 번 들어오면 최솟값만 남깁니다.

응용 패턴

경유 가능성(도달성) — min/+ 대신 or/and로 바꾸면 이행적 폐포
(Floyd-Warshall reachability)를 $$O(V^3)$$ 에 구합니다.
최소 사이클(가장 짧은 사이클 길이) — 갱신 도중 $$dist[i][k]+dist[k][j]+w(j,i)$$
형태로 사이클 길이를 추적.
경로 복원 — nxt[i][j]에 "i 다음 정점"을 저장해 경로를 복원.
병목 경로(최소 최대 간선) — +를 max로 바꾸면 미니맥스 경로.

작은 그래프에서 "모든 쌍"이 필요하면 가장 먼저 떠올릴 도구입니다. 짧지만
루프 순서 하나에 정답이 걸려 있다는 점을 늘 기억하세요.

Lesson 실전 가이드 — 모든 쌍 신호와 루프 순서의 이유 선택 8m

출제 신호

"모든 쌍 (또는 여러 출발점-도착점 조합)의 최단 거리" + $V \le 500$ .
이 정점 수 제한이 사실상 정답 공개입니다 — $O(V^3) = 1.25 \times 10^8$ 이
허용된다는 뜻이니까요.
"임의의 두 도시 사이", "어느 정점에서 출발해도", "거쳐서 가는 경로 포함"
거리 외의 변장: " $$i$$ 에서 $$j$$ 로 갈 수 있는가"(도달성 — 경로 행렬),
"두 사람 사이의 비교 관계를 몇 쌍이나 알 수 있는가"(순서 폐포),
"각 정점에서 가장 먼 정점", "그래프의 지름"
질의 수가 매우 많아( $Q \ge 10^5$ ) 매번 다익스트라를 돌릴 수 없을 때의
사전 계산용

$$V$$ 가 1000을 넘으면 $$V^3$$ 이 $$10^9$$ 를 넘으므로 정점별 다익스트라
( $O(V E \log V)$ )와 비교해 선택해야 합니다.

풀이 결정 절차

$$V^3$$ 을 계산해 시간 안인지 확인합니다 ( $V \le 500$ 안전, $V \approx 800$ 경계).
답이 거리인가, 도달성인가, 경로 자체인가 — 도달성이면 dist 대신 bool,
경로 복원이면 nxt[i][j](또는 경유점) 테이블을 함께 갱신합니다.
초기화를 설계합니다 — d[i][i] = 0, 간선 있으면 d[u][v] = w
(중복 간선은 min), 나머지 INF.
음수 간선은 허용되지만 음수 사이클이 있으면 결과가 무의미해집니다 —
판정이 필요하면 실행 후 d[i][i] < 0인 $$i$$ 를 찾습니다.

자주 하는 실수

루프 순서 — 경유점 $$k$$ 가 반드시 가장 바깥이어야 합니다. 점화식
$d_k[i][j] = \min(d_{k-1}[i][j],\ d_{k-1}[i][k] + d_{k-1}[k][j])$ 에서 $$k$$ 는
"여기까지의 경유점 허용 집합"이라는 DP 차원이기 때문입니다. $$i$$ 나 $$j$$ 를
바깥에 두면 일부 경로가 누락됩니다.

for (int k = 1; k <= n; k++)          // 경유점이 최외곽 — 순서가 본질
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

INF + INF 오버플로 — int에 INF = 2e9 근처를 쓰면 d[i][k]+d[k][j]가
넘칩니다. INF = 1e9처럼 두 배 해도 안전한 값을 쓰거나, 이완 전에
if (d[i][k] == INF || d[k][j] == INF) continue;를 넣으세요.
중복 간선을 마지막 값으로 덮어씀 — 입력에 같은 (u, v) 간선이 여러 번
오면 d[u][v] = min(d[u][v], w)로 받아야 합니다.
d[i][i] = 0 누락 — 자기 자신으로의 거리가 INF로 남아 경유 계산이 깨집니다.
경로 복원 테이블 갱신 누락 — 거리를 갱신할 때만 nxt[i][j] = nxt[i][k]로
같이 갱신해야 합니다. 거리 따로 경로 따로 만들면 어긋납니다.

연습 방법

사이드바 연습 목록의 기본 모든-쌍 거리 문제로 3중 루프와 초기화를 몸에
익힌 뒤, 도달성(경로 행렬) 변형과 경로 복원 문제로 확장하세요. "정점 수가
몇이면 플로이드인가"라는 감각( $\le 500$ )을 기르는 것이 이 단원의 절반입니다 —
문제를 보면 제약부터 확인하는 습관을 들이세요. 태그된 문제 3문제 이상
해결 시 마스터 처리되어 레이팅 CLASS 보너스에 반영됩니다.

Practice problem 경유 이득 노선 선택 25m

R00212

경유 이득 노선

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Practice problem 도시 간 이동 비용 선택 25m

R00211

도시 간 이동 비용

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Lesson DAG의 순서 세우기 필수 8m

어떤 문제를 푸는가

작업들 사이에 "A를 끝내야 B를 시작할 수 있다" 같은 의존 관계 가 있을 때,
모든 의존을 어기지 않는 하나의 직선 순서 를 찾는 것이 위상 정렬입니다.
선수 과목 수강 순서, 빌드 의존성, 컴파일 순서 등이 대표 예입니다.

의존 관계를 방향 간선 $u \to v$ ("u가 v보다 먼저")로 모으면 그래프가 됩니다.
위상 정렬이 가능하려면 이 그래프가 사이클이 없는 방향 그래프(DAG) 여야
합니다. 사이클이 있으면 순서를 정할 수 없습니다(서로 먼저여야 함).

방법 1 — 진입 차수 기반 (칸 알고리즘)

각 정점의 진입 차수(들어오는 간선 수)를 셉니다.

진입 차수 0인 정점들을 큐에 넣는다 (선행 작업이 없는 것들).
큐에서 하나 꺼내 결과에 추가하고, 그 정점에서 나가는 간선을 "제거"하며
이웃의 진입 차수를 1씩 줄인다.
새로 진입 차수가 0이 된 정점을 큐에 넣는다.
큐가 빌 때까지 반복.

정당성: 진입 차수 0인 정점은 어떤 선행 조건도 없으므로 지금 처리해도
안전합니다. 그 정점을 빼면 다른 정점들의 선행 조건이 하나씩 줄고, 그렇게
의존이 하나씩 풀려 나갑니다.

방법 2 — DFS 후위 순서 뒤집기

각 정점에서 DFS를 돌고, 함수가 끝나는(자식을 다 본) 순서 로 스택에 쌓은
뒤 뒤집습니다. 자식이 모두 끝난 뒤 부모가 쌓이므로, 뒤집으면 부모가 앞섭니다.

사이클 탐지

칸 알고리즘에서 결과에 들어간 정점 수가 $$V$$ 보다 작으면 사이클이 있습니다.
사이클 위의 정점들은 진입 차수가 끝내 0이 되지 못해 큐에 못 들어가기 때문입니다.

복잡도

항목	값
시간	$$O(V + E)$$
공간	$$O(V + E)$$

모든 간선과 정점을 상수 번 보므로 선형입니다.

답이 여러 개일 수 있다

진입 차수 0인 정점이 동시에 여러 개면 어느 것을 먼저 빼도 유효합니다. 따라서
위상 순서는 유일하지 않을 수 있습니다. "사전순으로 가장 빠른 순서" 같은
조건이 붙으면 큐 대신 우선순위 큐 를 씁니다. 다음 강의에서 구현과 응용을
봅니다.

Lesson 위상 정렬 구현과 DAG DP 선택 8m

칸 알고리즘 구현 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m; cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    vector<int> indeg(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;        // u → v
        adj[u].push_back(v);
        indeg[v]++;
    }

    priority_queue<int, vector<int>, greater<>> pq;   // 사전순이면 최소 힙
    for (int v = 1; v <= n; v++)
        if (indeg[v] == 0) pq.push(v);

    vector<int> order;
    while (!pq.empty()) {
        int u = pq.top(); pq.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (--indeg[v] == 0) pq.push(v);
    }

    if ((int)order.size() != n) { cout << "사이클 존재\n"; return 0; }
    for (int v : order) cout << v << ' ';
    cout << '\n';
}

사전순 조건이 없으면 그냥 queue를 써도 됩니다. 우선순위 큐를 쓰면
$O((V+E)\log V)$ 로 살짝 늘어납니다.

파이썬 구현

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
for _ in range(m):
    u, v = map(int, input().split())
    adj[u].append(v)
    indeg[v] += 1

q = deque(v for v in range(1, n + 1) if indeg[v] == 0)
order = []
while q:
    u = q.popleft()
    order.append(u)
    for v in adj[u]:
        indeg[v] -= 1
        if indeg[v] == 0:
            q.append(v)

print("사이클 존재" if len(order) != n else ' '.join(map(str, order)))

흔한 함정

사이클 미검출 — order 크기를 $$V$$ 와 비교해 사이클을 반드시 확인하세요.
사이클이 있는데 결과를 출력하면 오답입니다.
방향 혼동 — 간선 $u \to v$ 는 "u가 먼저"입니다. 문제의 의존 방향을
뒤집어 입력하지 않도록 주의.
진입 차수 갱신 시점 — --indeg[v] == 0일 때만 큐에 넣어야 중복 추가를
막습니다.

DAG 위에서의 DP — 위상 정렬의 진짜 힘

위상 순서대로 정점을 처리하면, 어떤 정점을 볼 때 그 정점으로 오는 모든
정점은 이미 처리되어 있습니다. 그래서 DAG 위의 최장 경로, 경로 수 세기,
누적 비용 같은 DP를 한 번의 순회로 깔끔하게 계산합니다.

// DAG 최장 경로 (모든 시작점)
for (int u : order)
    for (int v : adj[u])
        dp[v] = max(dp[v], dp[u] + 1);

일반 그래프의 최장 경로는 NP-난해지만, DAG에서는 위상 정렬 덕분에 선형
시간 에 풀린다는 점이 핵심입니다.

응용 패턴

선수 과목 / 빌드 순서 — 그대로 위상 정렬.
사이클 판정 — "순서를 매길 수 있는가"가 곧 "DAG인가".
DAG 경로 수 / 최장·최단 경로 — 위상 순서 DP.
사전순 최소 위상 순서 — 우선순위 큐.

"의존을 어기지 않는 순서"가 필요하면 위상 정렬, 그 순서 위에서 DP를 얹으면
의존 있는 계산이 단번에 풀립니다.

Lesson 실전 가이드 — 선후 관계 문장을 그래프로 옮기기 선택 8m

출제 신호

위상 정렬은 문장 신호가 또렷합니다.

" $$A$$ 를 먼저 해야 $$B$$ 를 할 수 있다" — 선수 과목, 건물 건설 순서, 작업 의존성
"키 비교 결과들이 주어질 때 줄 세우기", "일부 쌍의 순서만 알 때 가능한 나열"
"모든 작업을 끝내는 최소 시간" (의존성 + 소요 시간 → 위상 순서로 DP)
"순서가 모순인지(사이클) 판정하라"

그래프가 방향이고 사이클이 없어야(DAG) 한다는 게 전제입니다. 문제가
사이클 가능성을 열어 두었다면 "불가능 판정"까지가 과제에 포함된 것입니다.
$V, E \le 10^5{\sim}10^6$ 에서도 $$O(V + E)$$ 라 규모 부담이 없습니다.

풀이 결정 절차

문장 속 "먼저/이후/의존" 관계를 간선 방향으로 번역합니다 — "A 먼저, B 나중"은
$A \to B$ , 그리고 indeg[B]++.
출력 요구를 확인합니다 — (a) 아무 위상 순서나 하나, (b) 사전순 최소
(큐를 최소 힙으로 교체, $O(E \log V)$ ), © 순서가 유일한지 판정
(큐 크기가 항상 1인지 확인).
위에 DP가 얹히는지 봅니다 — "최소 완료 시간"은
time[v] = max(time[u] for u→v) + cost[v]를 위상 순서대로 계산합니다.
max를 빼먹고 마지막 부모만 반영하는 실수가 흔합니다.
사이클 판정 방법을 정합니다 — 결과에 담긴 정점 수가 $$V$$ 미만이면 사이클.

자주 하는 실수

사이클 판정 누락 — 큐가 비어도 모든 정점을 처리했다는 보장이 없습니다.

from collections import deque

q = deque(v for v in range(1, n + 1) if indeg[v] == 0)
order = []
while q:
    u = q.popleft()
    order.append(u)
    for v in adj[u]:
        indeg[v] -= 1
        if indeg[v] == 0:
            q.append(v)

if len(order) < n:        # 처리 못 한 정점 = 사이클에 갇힌 정점
    print(-1)

간선 방향 반대로 — "B는 A 이후"를 $B \to A$ 로 넣는 번역 실수. 작은
예제로 순서가 뒤집혀 나오면 십중팔구 이것입니다.
indeg 0 정점을 시작에 전부 넣지 않음 — 시작점이 하나라고 가정하면
여러 컴포넌트가 있는 입력에서 틀립니다.
중복 간선 — 같은 의존이 두 번 주어지면 indeg가 2 올라갑니다. 문제에
따라 중복 제거가 필요한지 확인하세요.
사전순 요구를 못 보고 deque 사용 — "여러 답 중 사전순으로 가장 빠른
것"이라는 문장이 있으면 heapq로 바꿔야 합니다.
DP 변형에서 max 대신 마지막 갱신값 사용 — 완료 시간은 모든 선행
작업의 최댓값 기준입니다. time[v] = max(time[v], time[u] + cost[v]).

연습 방법

사이드바 연습 목록의 기본 줄 세우기 문제로 큐 기반 칸(Kahn) 구현을 익히고,
사전순 최소(힙 교체) → 완료 시간 DP(건물 짓기류) → 유일성 판정 순서로
확장하세요. 문제를 읽으며 "무엇이 정점이고, '먼저'가 어느 방향 간선인가"를
한 줄로 적고 시작하는 습관이 번역 실수를 막아 줍니다. 태그된 문제
3문제 이상 해결 시 마스터 처리되어 레이팅 CLASS 보너스에 반영됩니다.

Practice problem 물류 작업 병렬 처리 선택 25m

R00216

물류 작업 병렬 처리

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Practice problem 문제집 선택 25m

R00757

문제집

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Level 5 · Analyst

Analyst

그래프 이론 · Analyst 단계

0/30 완료

Lesson SCC와 응축 그래프: 정의와 이론 필수 8m

강한 연결 요소란

방향 그래프에서 두 정점 $$u, v$$ 가 서로 도달 가능하면( $u \to v$ 경로와 $v \to u$ 경로가 모두 존재) 같은 강한 연결 요소(Strongly Connected Component, SCC) 에 속한다. "서로 도달 가능"은 동치 관계이므로, 정점 집합은 SCC들로 완전히 분할된다.

각 SCC를 하나의 정점으로 압축하면 응축 그래프(condensation) 를 얻는다.

정리. 응축 그래프는 항상 DAG(사이클 없는 방향 그래프)다.

증명: 응축 그래프에 사이클 $C_1 \to C_2 \to \dots \to C_k \to C_1$ 이 있다면 이 SCC들의 모든 정점이 서로 도달 가능해져 하나의 SCC로 합쳐졌을 것이므로 모순이다. 이 성질 덕분에 "방향 그래프의 전역 구조 = SCC로 압축한 DAG"라는 강력한 관점을 얻는다.

언제 쓰나

방향 그래프에서 "서로 오갈 수 있는 그룹" 판정.
2-SAT: 함의 그래프의 SCC로 만족 가능성 판정.
위상적 성질이 필요한데 사이클이 있는 그래프 → 응축 후 DAG DP.
도달성 축약, 필수 정점/간선 분석의 전처리.

시간 복잡도는 $$O(V + E)$$ 로 선형이다.

타잔(Tarjan)의 아이디어

한 번의 DFS로 SCC를 모두 찾는다. 각 정점에 방문 순서 $\mathrm{disc}[u]$ (발견 시각)를 부여하고,

$\mathrm{low}[u] = \min\big(\mathrm{disc}[u],\ \min_{(u,v)\ \text{back/tree, } v\ \text{on stack}} \mathrm{low}[v]\big)$

즉 $$u$$ 의 서브트리에서 아직 스택에 남아 있는 정점을 통해 도달할 수 있는 가장 작은 $\mathrm{disc}$ 값을 저장한다. 방문 중인 정점들을 스택에 쌓아 두었다가, DFS 종료 시 $\mathrm{low}[u] = \mathrm{disc}[u]$ 인 $$u$$ 가 나오면 $$u$$ 는 자기 SCC의 "뿌리"이고, 스택에서 $$u$$ 까지 팝한 정점들이 하나의 SCC를 이룬다.

핵심은 "스택에 남아 있는 정점만" $\mathrm{low}$ 갱신에 쓴다는 것이다. 이미 다른 SCC로 확정되어 스택에서 빠진 정점(교차 간선의 대상)은 무시해야 한다.

코사라주(Kosaraju)

더 이해하기 쉬운 대안: (1) 원본 그래프에서 DFS하여 종료 순서(post-order)를 스택에 기록, (2) 역방향 그래프에서 스택의 역순(종료가 늦은 것부터)으로 DFS — 한 번의 DFS가 훑는 정점 집합이 정확히 하나의 SCC다. DFS를 두 번 하지만 여전히 $$O(V+E)$$ 다.

작은 예제

간선 $0\to1,\ 1\to2,\ 2\to0,\ 2\to3,\ 3\to4,\ 4\to5,\ 5\to3$ , 그리고 고립 정점 $$6$$ .

$\{0,1,2\}$ — 삼각 사이클로 서로 도달 가능.
$\{3,4,5\}$ — 마찬가지로 사이클.
$\{6\}$ — 단독.

응축 그래프는 $\{0,1,2\} \to \{3,4,5\}$ 한 개의 간선을 가진 DAG이며, $\{6\}$ 은 고립점이다. SCC는 총 3개다.

Lesson 타잔·코사라주 구현 선택 8m

타잔 구현 (C++)

DFS 재귀 한 번으로 SCC를 확정한다. onstk로 스택 잔류 여부를 관리하는 것이 정확성의 핵심이다. comp[v]가 작을수록 응축 DAG의 위상적으로 뒤쪽(타잔은 SCC를 위상 역순으로 확정)임에 유의한다.

#include <bits/stdc++.h>
using namespace std;

int n;                       // 정점 수
vector<vector<int>> g;       // 인접 리스트
vector<int> disc, low, comp; // 발견시각, low값, SCC 번호
vector<bool> onstk;
stack<int> st;
int timer_ = 0, sccCnt = 0;

void dfs(int u) {
    disc[u] = low[u] = ++timer_;
    st.push(u); onstk[u] = true;
    for (int v : g[u]) {
        if (!disc[v]) {                 // 트리 간선
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (onstk[v]) {          // 스택에 남은 정점 → back/cross
            low[u] = min(low[u], disc[v]);
        }
    }
    if (low[u] == disc[u]) {            // u는 SCC의 뿌리
        while (true) {
            int x = st.top(); st.pop(); onstk[x] = false;
            comp[x] = sccCnt;
            if (x == u) break;
        }
        sccCnt++;
    }
}

void tarjan() {
    disc.assign(n, 0); low.assign(n, 0);
    comp.assign(n, -1); onstk.assign(n, false);
    for (int i = 0; i < n; i++) if (!disc[i]) dfs(i);
}

위 예제로 실행하면 sccCnt = 3, $\{0,1,2\}$ 가 같은 번호, $\{3,4,5\}$ 가 같은 번호, $\{6\}$ 이 단독으로 나온다.

코사라주 구현 (C++)

vector<vector<int>> g, gr;   // 원본, 역방향
vector<bool> vis; vector<int> order_, comp; int n, sccCnt = 0;

void dfs1(int u){ vis[u]=true; for(int v:g[u]) if(!vis[v]) dfs1(v); order_.push_back(u); }
void dfs2(int u,int c){ comp[u]=c; for(int v:gr[u]) if(comp[v]<0) dfs2(v,c); }

void kosaraju(){
    vis.assign(n,false); comp.assign(n,-1); order_.clear();
    for(int i=0;i<n;i++) if(!vis[i]) dfs1(i);
    for(int i=n-1;i>=0;i--){ int u=order_[i]; if(comp[u]<0) dfs2(u, sccCnt++); }
}

Python (반복형 타잔)

파이썬은 재귀 깊이 제한( $$10^4$$ 부근)과 느린 재귀 때문에 큰 그래프에서 반복형이 안전하다.

import sys

def tarjan_scc(n, g):
    disc = [0] * n; low = [0] * n; comp = [-1] * n
    onstk = [False] * n; st = []; timer = 1; scc = 0
    for s in range(n):
        if disc[s]:
            continue
        stack = [(s, 0)]                 # (정점, 다음에 볼 간선 인덱스)
        while stack:
            u, i = stack[-1]
            if i == 0:
                disc[u] = low[u] = timer; timer += 1
                st.append(u); onstk[u] = True
            if i < len(g[u]):
                stack[-1] = (u, i + 1)
                v = g[u][i]
                if not disc[v]:
                    stack.append((v, 0))
                elif onstk[v]:
                    low[u] = min(low[u], disc[v])
            else:
                if low[u] == disc[u]:
                    while True:
                        x = st.pop(); onstk[x] = False; comp[x] = scc
                        if x == u:
                            break
                    scc += 1
                stack.pop()
                if stack:
                    low[stack[-1][0]] = min(low[stack[-1][0]], low[u])
    return scc, comp

응축 그래프 만들기

SCC 번호가 정해지면 간선 $$(u,v)$$ 에서 $\mathrm{comp}[u] \ne \mathrm{comp}[v]$ 인 것만 모아 중복 제거하면 응축 DAG가 된다. 타잔의 comp 번호는 위상 역순이므로, 응축 DAG를 위상 순서로 처리하려면 번호 내림차순으로 보면 된다.

Lesson 심화: 응축 DP·2-SAT·함정 선택 8m

응축 후 DAG DP

SCC의 진짜 위력은 "사이클 있는 방향 그래프 문제 → 응축 → DAG 문제"라는 환원에 있다.

최장 경로 / 도달 가능한 최대 가중치: 각 SCC의 내부 이득을 노드 가중치로 삼아 응축 DAG에서 DP.
소스/싱크 SCC 세기: 응축 DAG에서 진입차수 0(소스), 진출차수 0(싱크)인 SCC. "모든 정점이 서로 도달 가능하게 만들려면 최소 몇 개의 간선을 추가?" → $\max(\text{소스 수}, \text{싱크 수})$ (단, SCC가 1개면 0).
위상 정렬 가능 여부: SCC가 모두 크기 1이면 원본이 DAG.

2-SAT 연결

$$n$$ 개의 불리언 변수에 대한 2-CNF의 만족 가능성은 SCC로 판정한다. 각 변수 $$x$$ 에 정점 $$x$$ 와 $\lnot x$ 를 두고, 절 $(a \lor b)$ 를 함의 $\lnot a \to b$ , $\lnot b \to a$ 두 간선으로 표현한 함의 그래프를 만든다.

정리. 2-CNF가 만족 불가능 $\iff$ 어떤 변수 $$x$$ 에 대해 $$x$$ 와 $\lnot x$ 가 같은 SCC에 있다.

만족 가능하면 SCC 위상 순서상 $\lnot x$ 보다 뒤에 오는 쪽을 참으로 두면 된다(타잔의 comp 번호가 작을수록 위상 뒤이므로 comp[x] > comp[¬x]이면 $$x =$$ 참). 자세한 내용은 2-SAT 강의 참고.

흔한 실수와 엣지 케이스

스택 잔류 검사 누락: else if (onstk[v]) 조건을 빼고 그냥 low[u]=min(low[u],disc[v])를 하면, 이미 다른 SCC로 확정된 정점(교차 간선)을 잘못 끌어와 SCC를 과하게 합친다. 반드시 onstk[v] 확인.
low 갱신에 disc[v] vs low[v]: back/cross 간선에서는 disc[v]를, 트리 간선(재귀 후)에서는 low[v]를 쓴다. 둘을 섞으면 미묘한 오류가 난다(정답이 나오는 경우도 있어 발견이 어렵다). 위 코드처럼 구분하라.
재귀 깊이: C++에서도 $V \sim 10^5$ 사슬 그래프면 스택 오버플로가 날 수 있다. 반복형으로 바꾸거나 스택 크기를 늘린다(ulimit -s).
자기 루프 $u\to u$ : SCC 판정에는 영향 없다( $$u$$ 는 이미 자기 SCC). 하지만 "SCC가 사이클을 가지는가(간선 $\ge 1$ )"를 물으면 자기 루프나 크기 $\ge 2$ 인 SCC를 따로 판별해야 한다.
다중 간선: 정확성에는 무해하다. 응축 그래프를 만들 때만 중복 제거하면 된다.
방향성: SCC는 방향 그래프 개념이다. 무방향 그래프의 "연결 요소"는 단순 DFS/Union-Find로 충분하고, "이중 연결 요소"는 별도 개념(단절점 강의 참고)이다.

코사라주 vs 타잔

항목	타잔	코사라주
DFS 횟수	1회	2회
역그래프 필요	아니오	예
SCC 번호 순서	위상 역순	위상 순서(2차 DFS 순)
구현 난도	중(스택/low)	하

둘 다 $$O(V+E)$$ 이며 실전에서는 취향 차이다. 함의 그래프처럼 역그래프 만들기 번거로운 경우 타잔이, 개념을 명확히 하고 싶으면 코사라주가 편하다.

Practice problem 강한 연결 요소의 개수 선택 25m

R00371

강한 연결 요소의 개수

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Practice problem 진영 배치 호환성 선택 25m

R00658

진영 배치 호환성

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

플래티넘 IV 지금 풀기

Lesson 함의 그래프와 SCC 판정 정리 필수 8m

2-SAT 문제

각 절(clause)이 리터럴 2개의 논리합으로 이뤄진 CNF(2-CNF)의 만족 가능성(satisfiability)을 묻는 문제다. 예:

$(x_0 \lor x_1) \land (\lnot x_0 \lor x_1) \land (\lnot x_1 \lor \lnot x_0)$

각 변수에 참/거짓을 배정해 모든 절을 참으로 만들 수 있는가? 일반 SAT는 NP-완전이지만, 절의 리터럴이 2개로 제한된 2-SAT는 $$O(V+E)$$ 선형 시간에 풀린다. 여기서 $$V = 2n$$ (변수 $$n$$ 개 × 참/거짓), $$E$$ 는 절 수의 상수배다.

함의 그래프

핵심 관찰: 절 $(a \lor b)$ 는 두 개의 함의와 동치다.

$(a \lor b) \equiv (\lnot a \to b) \land (\lnot b \to a)$

" $$a$$ 가 거짓이면 $$b$$ 는 반드시 참"이라는 뜻이다. 그래서 각 리터럴을 정점으로 하는 함의 그래프(implication graph) 를 만든다. 정점은 $$2n$$ 개: 변수 $$x_i$$ 마다 " $$x_i$$ 참" 노드와 " $$x_i$$ 거짓( $\lnot x_i$ )" 노드.

절 $(a \lor b)$ 마다 간선 $\lnot a \to b$ , $\lnot b \to a$ 두 개를 추가한다. 리터럴 하나만 강제(단위 절 $$a$$ )하려면 $\lnot a \to a$ 하나를 넣으면 된다(" $$a$$ 가 거짓이라 가정하면 즉시 $$a$$ 가 참이어야 함 → 모순"이라 $$a$$ 는 참으로 강제됨).

판정 정리

함의는 추이적( $a\to b,\ b\to c \Rightarrow a\to c$ )이므로, 같은 SCC 안의 리터럴들은 모두 같은 진릿값을 가져야 한다(서로가 서로를 강제).

정리. 2-CNF가 만족 불가능 $\iff$ 어떤 변수 $$x_i$$ 에 대해 $$x_i$$ 와 $\lnot x_i$ 가 같은 SCC에 있다.

$$x_i$$ 와 $\lnot x_i$ 가 같은 SCC면 둘이 같은 값을 가져야 하는데 그건 모순이므로 UNSAT. 그렇지 않으면 항상 해가 존재하며, 배정 규칙은:

배정. 함의 그래프를 SCC로 응축하면 DAG가 된다. 각 변수 $$x_i$$ 에 대해 위상적으로 더 뒤에 있는 SCC 쪽 리터럴을 참으로 둔다.

직관: $\lnot x_i \to x_i$ 방향의 함의 사슬이 있으면 $$x_i$$ 를 참으로 두어야 모순이 없다. "위상 뒤쪽을 참"으로 두면 "참 리터럴에서 거짓 리터럴로 가는 간선"이 생기지 않음을 보일 수 있다. 함의 그래프의 대칭성( $a\to b$ 가 있으면 $\lnot b \to \lnot a$ 도 항상 존재)이 이 규칙의 정당성을 보장한다.

작은 예제

위의 3-절 예제: $(x_0\lor x_1),(\lnot x_0\lor x_1),(\lnot x_1\lor \lnot x_0)$ .

세 번째 절에서 $$x_0,x_1$$ 을 동시에 참으로 둘 수 없다.
두 번째 절과 첫 절을 함께 보면 $$x_1$$ 이 참이어야 편하다.
배정: $x_1 = \text{참},\ x_0 = \text{거짓}$ → 세 절 모두 참. SAT.

반면 단위 절 $$x_0$$ 과 $\lnot x_0$ 을 동시에 강제하면 $x_0,\lnot x_0$ 이 한 SCC로 묶여 UNSAT.

Lesson 정점 인코딩과 구현 선택 8m

정점 인코딩

변수 $$i$$ 의 두 리터럴을 정수로 매핑한다. 흔한 두 방식:

$$2i$$ = " $$x_i$$ 참", $$2i+1$$ = " $$x_i$$ 거짓". 부정은 $\oplus 1$ .
$$i$$ = 참, $$i+n$$ = 거짓.

아래는 첫 방식이다. SCC는 코사라주(역그래프 2회 DFS)로 구해 위상 순서를 직접 얻는다. comp 값이 클수록 위상 뒤쪽이 되게 코사라주를 짜면, 배정은 "comp[참] > comp[거짓]이면 참"이 된다.

#include <bits/stdc++.h>
using namespace std;

struct TwoSAT {
    int n;
    vector<vector<int>> g, gr;
    vector<int> comp, order_;
    vector<bool> vis;
    vector<char> val;                     // 결과 배정
    TwoSAT(int vars): n(vars), g(2*vars), gr(2*vars),
        comp(2*vars, -1), vis(2*vars, false), val(vars) {}

    int node(int x, bool t){ return 2*x + (t ? 0 : 1); }  // t=참 노드
    void addImpl(int x, bool xt, int y, bool yt){          // (x=xt) -> (y=yt)
        g[node(x,xt)].push_back(node(y,yt));
        gr[node(y,yt)].push_back(node(x,xt));
    }
    void addClause(int x, bool xt, int y, bool yt){        // (x=xt) OR (y=yt)
        addImpl(x, !xt, y, yt);
        addImpl(y, !yt, x, xt);
    }
    void addTrue(int x, bool xt){ addImpl(x, !xt, x, xt); } // x=xt 를 강제

    void dfs1(int u){ vis[u]=true; for(int v:g[u]) if(!vis[v]) dfs1(v); order_.push_back(u); }
    void dfs2(int u,int c){ comp[u]=c; for(int v:gr[u]) if(comp[v]<0) dfs2(v,c); }

    bool solve(){
        for(int i=0;i<2*n;i++) if(!vis[i]) dfs1(i);
        int c=0;
        for(int i=2*n-1;i>=0;i--){ int u=order_[i]; if(comp[u]<0) dfs2(u, c++); }
        for(int i=0;i<n;i++){
            if(comp[2*i]==comp[2*i+1]) return false;  // x_i 와 ¬x_i 가 같은 SCC → UNSAT
            val[i] = comp[2*i] > comp[2*i+1];          // 위상 뒤쪽(번호 큰 쪽)을 참
        }
        return true;
    }
};

사용 예:

TwoSAT ts(2);
ts.addClause(0,true, 1,true);   // (x0 ∨ x1)
ts.addClause(0,false,1,true);   // (¬x0 ∨ x1)
ts.addClause(1,false,0,false);  // (¬x1 ∨ ¬x0)
if(ts.solve()) /* val = {0,1}: x0=거짓, x1=참 */;

이 코드는 위 예제에서 x0=0, x1=1을 반환하고, $x_0 \land \lnot x_0$ 강제 시 false(UNSAT)를 반환한다.

Python

import sys
class TwoSAT:
    def __init__(self, n):
        self.n = n
        self.g = [[] for _ in range(2*n)]
        self.gr = [[] for _ in range(2*n)]
    def node(self, x, t): return 2*x + (0 if t else 1)
    def add_impl(self, x, xt, y, yt):
        self.g[self.node(x, xt)].append(self.node(y, yt))
        self.gr[self.node(y, yt)].append(self.node(x, xt))
    def add_clause(self, x, xt, y, yt):
        self.add_impl(x, not xt, y, yt)
        self.add_impl(y, not yt, x, xt)
    def solve(self):
        n2 = 2 * self.n
        vis = [False]*n2; order = []
        for s in range(n2):                 # 반복형 DFS (post-order)
            if vis[s]: continue
            stk = [(s, 0)]
            while stk:
                u, i = stk[-1]
                if i == 0: vis[u] = True
                if i < len(self.g[u]):
                    stk[-1] = (u, i+1); v = self.g[u][i]
                    if not vis[v]: stk.append((v, 0))
                else:
                    order.append(u); stk.pop()
        comp = [-1]*n2; c = 0
        for u in reversed(order):
            if comp[u] >= 0: continue
            stk = [u]; comp[u] = c
            while stk:
                x = stk.pop()
                for y in self.gr[x]:
                    if comp[y] < 0: comp[y] = c; stk.append(y)
            c += 1
        val = [False]*self.n
        for i in range(self.n):
            if comp[2*i] == comp[2*i+1]: return None
            val[i] = comp[2*i] > comp[2*i+1]
        return val

두 SCC 방식(타잔/코사라주) 모두 가능하나, 위상 순서를 배정에 직접 써야 하므로 코사라주가 편하다. 타잔을 쓰면 comp 번호가 위상 역순이므로 배정 조건이 comp[참] < comp[거짓]으로 뒤집힌다.

Lesson 심화: 모델링 패턴·at-most-one·함정 선택 8m

자주 쓰는 모델링 패턴

2-SAT의 힘은 "각 대상이 두 상태 중 하나"인 제약을 절로 바꾸는 데 있다.

자연어 제약	절 / 함의
$$a$$ 또는 $$b$$ 중 적어도 하나 참	$(a \lor b)$
$$a$$ 이면 $$b$$	$(\lnot a \lor b)$
$$a$$ 와 $$b$$ 중 최대 하나만 참	$(\lnot a \lor \lnot b)$
$$a$$ 와 $$b$$ 는 같은 값	$(a\lor\lnot b)\land(\lnot a\lor b)$
$$a$$ 와 $$b$$ 는 다른 값(XOR)	$(a\lor b)\land(\lnot a\lor\lnot b)$
$$a$$ 를 참으로 강제	$\lnot a \to a$

"최대 하나만 참"의 규모 축소

$$k$$ 개 리터럴 $\ell_1,\dots,\ell_k$ 중 최대 하나만 참(at-most-one)을 순진하게 $\binom{k}{2}$ 개 절로 넣으면 $$O(k^2)$$ 다. 접두사 보조 변수 $$p_i$$ (" $\ell_1..\ell_i$ 중 하나라도 참")를 도입하면 $$O(k)$$ 절로 줄인다:

$\ell_i \to p_i,\quad p_{i-1}\to p_i,\quad p_{i-1}\to \lnot\ell_i.$

정점/구간이 많은 스케줄링·좌표 배치 문제에서 이 축소가 시간 제한을 가른다.

대표적 응용

구간/좌표 이진 선택: 각 원소를 두 위치(또는 켜짐/꺼짐) 중 하나로 놓되 충돌 쌍을 $(\lnot a \lor \lnot b)$ 로 금지.
불리언 게임/제약 충족: "이 스위치를 켜면 저 스위치는 꺼야 한다" 류.
한 변수의 강제: 답을 이분 탐색하며 "현재 임계값에서 2-SAT이 만족되는가"를 판정하는 매개변수 탐색과 결합.

엣지 케이스와 흔한 버그

위상 방향 혼동: SCC 방식에 따라 "참으로 둘 쪽"이 뒤집힌다. 코사라주(2차 DFS 순 = 위상 순)면 comp[참] > comp[거짓], 타잔이면 반대. 한쪽으로 통일하고 작은 예제로 반드시 검증하라.
단위 절 인코딩: " $$a$$ 는 반드시 참"은 $\lnot a \to a$ 하나다. 실수로 $a \to \lnot a$ 까지 넣으면 즉시 UNSAT이 된다.
대칭 간선 누락: 절 하나당 함의는 두 개( $\lnot a\to b$ , $\lnot b\to a$ )다. 하나만 넣으면 함의 그래프의 대칭성이 깨져 배정 규칙이 틀린다.
자기 자신과의 절: $(a \lor a)$ 는 " $$a$$ 참 강제"와 같다( $\lnot a \to a$ ). 코드가 이를 자연히 처리하는지 확인.
변수/리터럴 인덱싱 오프바이원: $$2i / 2i+1$$ 방식과 $$i / i+n$$ 방식을 섞지 말 것. node(), 부정 연산( $\oplus 1$ vs $\pm n$ )을 한 규칙으로 고정.
해의 유일성: 2-SAT은 아무 만족 배정 하나를 준다. "최소 참 개수" 등 최적화는 일반적으로 2-SAT 범위 밖(그건 별도 기법 필요).

2-SAT은 결국 함의 그래프의 SCC로 귀결되므로, SCC 강의(타잔/코사라주)를 확실히 익혀 두면 구현·디버깅이 훨씬 수월하다.

Practice problem 진영 배치 호환성 선택 25m

R00658

진영 배치 호환성

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

플래티넘 IV 지금 풀기

Practice problem 스위치와 램프 선택 25m

R00388

스위치와 램프

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Lesson 단절점·단절선의 판정 이론 필수 8m

단절점과 단절선

무방향 연결 그래프에서,

단절점(articulation point, cut vertex): 그 정점(과 붙은 간선)을 지우면 연결 요소가 늘어나는 정점.
단절선(bridge, cut edge): 그 간선을 지우면 연결 요소가 늘어나는 간선.

이들은 그래프의 "취약점"이다. 통신망에서 끊기면 분단이 일어나는 지점, 도로망의 필수 교차로/다리 등을 찾을 때 쓴다. DFS 한 번, $$O(V+E)$$ 에 모두 찾는다.

DFS 트리와 lowlink

무방향 그래프를 DFS하면 트리 간선과 역간선(back edge) 만 생긴다(교차 간선 없음). 각 정점에 발견 시각 $\mathrm{disc}[u]$ 를 주고,

$\mathrm{low}[u] = \min\Big(\mathrm{disc}[u],\ \min_{\text{역간선 }(u,w)} \mathrm{disc}[w],\ \min_{\text{자식 }v} \mathrm{low}[v]\Big)$

즉 $$u$$ 의 서브트리에서 역간선을 타고 올라갈 수 있는 가장 높은(작은 $\mathrm{disc}$ ) 조상까지의 값이다.

단절선 판정. 트리 간선 $$(u,v)$$ ( $$v$$ 는 자식)에 대해 $\mathrm{low}[v] > \mathrm{disc}[u]$ 이면 $$(u,v)$$ 는 단절선. ( $$v$$ 의 서브트리가 $$u$$ 를 거치지 않고는 위로 못 올라감.)

단절점 판정.
- 루트가 아닌 $$u$$ : 어떤 자식 $$v$$ 에 대해 $\mathrm{low}[v] \ge \mathrm{disc}[u]$ 이면 $$u$$ 는 단절점.
- 루트 $$u$$ : DFS 트리에서 자식이 2개 이상이면 단절점.

단절선은 $$>$$ (부등호 엄격), 단절점은 $\ge$ 임에 주의. 다리는 "위로 전혀 못 올라감", 단절점은 " $$u$$ 보다 위로는 못 올라감"이라 조건이 미묘하게 다르다.

이중 연결 요소(BCC)

이중 연결(2-vertex-connected): 단절점이 없어, 임의의 두 정점 사이에 정점-서로소인 경로가 2개 이상 존재. 이중 연결 요소(biconnected component) 는 이 성질을 갖는 극대 부분그래프다.

BCC는 보통 간선의 분할로 정의한다(정점은 단절점을 통해 여러 BCC에 공유됨). 각 BCC는 하나의 사이클로 얽힌 "덩어리"이고, 서로 다른 BCC는 단절점 하나만 공유한다. 단절선 하나는 그 자체로 크기 1(간선 하나)짜리 BCC를 이룬다.

블록-컷 트리

BCC(블록)들과 단절점들을 정점으로 삼아, "단절점 $$c$$ 가 블록 $$B$$ 에 속하면 $$c$$ – $$B$$ 를 잇는" 블록-컷 트리(block-cut tree) 를 만들면 그래프의 2-연결 구조가 트리로 정리된다. 이 트리는 "어떤 두 정점을 잇는 경로가 반드시 지나는 단절점" 같은 질의를 트리 문제로 바꿔 준다.

작은 예제

삼각형 $0\!-\!1\!-\!2\!-\!0$ , 다리 $2\!-\!3$ , 삼각형 $3\!-\!4\!-\!5\!-\!3$ .

단절점: $$2$$ (첫 삼각형과 나머지를 이음), $$3$$ (다리와 둘째 삼각형을 이음).
단절선: $$(2,3)$$ 하나.
BCC: 삼각형 $\{0,1,2\}$ 의 간선들, 다리 $\{2,3\}$ , 삼각형 $\{3,4,5\}$ 의 간선들 — 총 3개.

Lesson 구현과 BCC 추출 선택 8m

단절점·단절선·BCC 추출 (C++)

간선에 고유 id를 부여하고 간선 스택을 유지하면, 단절점 조건( $\mathrm{low}[v]\ge\mathrm{disc}[u]$ )이 성립하는 순간 스택에서 방금 간선까지 팝하여 하나의 BCC를 얻는다. 부모 간선 id로 역행을 막아 다중 간선도 올바로 처리한다.

#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<pair<int,int>>> g;        // (인접정점, 간선id)
vector<int> disc, low;
vector<bool> isArt;
int timer_ = 0;
vector<pair<int,int>> bridges;
vector<vector<int>> bccs;               // 각 원소: 간선 id 목록
stack<int> est;                         // 간선 스택

void dfs(int u, int pe) {               // pe: 부모로 이어진 간선 id
    disc[u] = low[u] = ++timer_;
    int child = 0;
    for (auto [v, id] : g[u]) {
        if (id == pe) continue;         // 부모 간선으로 되돌아가지 않음
        if (!disc[v]) {                 // 트리 간선
            est.push(id); child++;
            dfs(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > disc[u]) bridges.push_back({u, v});
            if ((pe == -1 && child > 1) || (pe != -1 && low[v] >= disc[u]))
                isArt[u] = true;
            if (low[v] >= disc[u]) {    // u는 이 BCC의 경계 → 스택에서 뽑아냄
                vector<int> comp; int x;
                do { x = est.top(); est.pop(); comp.push_back(x); } while (x != id);
                bccs.push_back(comp);
            }
        } else if (disc[v] < disc[u]) { // 위로 향하는 역간선만 스택에
            est.push(id);
            low[u] = min(low[u], disc[v]);
        }
    }
}

void run() {
    disc.assign(n, 0); low.assign(n, 0); isArt.assign(n, false);
    for (int i = 0; i < n; i++) if (!disc[i]) dfs(i, -1);
}

간선은 id로 관리하며 무방향 그래프이므로 각 간선을 g[a]와 g[b] 양쪽에 같은 id로 넣는다:

void addEdge(int id, int a, int b){ g[a].push_back({b,id}); g[b].push_back({a,id}); }

위 예제에서 이 코드는 단절점 $\{2,3\}$ , 단절선 $$(2,3)$$ , BCC 3개를 정확히 출력한다.

Python (반복형)

큰 그래프에선 재귀 한계 때문에 반복형이 안전하다. 아래는 단절점·단절선만 뽑는 간결 버전.

def cut_points_bridges(n, adj):   # adj[u] = [(v, edge_id), ...]
    disc = [0]*n; low = [0]*n; is_art = [False]*n
    bridges = []; timer = 1
    for s in range(n):
        if disc[s]: continue
        stk = [(s, -1, 0)]        # (정점, 부모간선, 자식카운터/이터레이터 위치)
        it = [0]*n; child = [0]*n; parent = [-1]*n; pe = [-1]*n
        stk = [(s, -1)]
        disc[s] = low[s] = timer; timer += 1
        while stk:
            u, pedge = stk[-1]
            if it[u] < len(adj[u]):
                v, eid = adj[u][it[u]]; it[u] += 1
                if eid == pedge: continue
                if not disc[v]:
                    parent[v] = u; pe[v] = eid; child[u] += 1
                    disc[v] = low[v] = timer; timer += 1
                    stk.append((v, eid))
                elif disc[v] < disc[u]:
                    low[u] = min(low[u], disc[v])
            else:
                stk.pop()
                p = parent[u]
                if p != -1:
                    low[p] = min(low[p], low[u])
                    if low[u] > disc[p]:
                        bridges.append((p, u))
                    if parent[p] != -1 and low[u] >= disc[p]:
                        is_art[p] = True
                if p == -1 and child[u] > 1:
                    is_art[u] = True   # 루트: 자식 2개↑
    return is_art, bridges

무엇을 뽑느냐에 따라

단절점만 필요: 간선 스택 없이 위 판정만.
단절선만 필요: low[v] > disc[u] 조건만. (부모 간선 대신 다중 간선을 세는 방식도 있으나, 간선 id로 막는 편이 안전.)
BCC(정점 이중연결): 간선 스택으로 추출.
2-edge-connected component(단절선 제거 후 요소): 단절선만 지우고 남은 연결 요소를 세면 된다 → 다리 트리 참고(3강).

Lesson 심화: 다리 트리·블록-컷 트리·함정 선택 8m

다리 트리(bridge tree)

모든 단절선을 지우면 그래프는 여러 2-edge-connected component(내부에 다리가 없는 덩어리)로 쪼개진다. 각 덩어리를 한 정점으로 축약하고 단절선으로 이으면 다리 트리가 된다.

다리 트리의 두 정점 사이 경로 위 간선 수 = 원본에서 두 정점을 분리하려면 끊어야 하는 최소 다리 수.
"임의의 두 정점 간 간선-서로소 경로가 2개 이상이 되도록 최소 몇 개의 간선을 추가?" → 다리 트리의 잎 개수 $$L$$ 에 대해 $\lceil L/2 \rceil$ .

구현: 단절선을 표시 → 단절선이 아닌 간선으로만 연결 요소(덩어리) 번호 매기기(BFS/DFS 또는 DSU) → 덩어리 번호로 축약 그래프 구성.

블록-컷 트리 활용

블록-컷 트리는 "두 정점을 잇는 모든 경로가 반드시 지나는 단절점"을 트리 경로로 답한다. 정점 이중연결 관련 질의(정점-서로소 경로 2개 존재 여부, 필수 통과 정점 등)에 유용하다.

엣지 케이스와 흔한 버그

단절선 vs 단절점 부등호: 다리는 $\mathrm{low}[v] > \mathrm{disc}[u]$ (엄격), 단절점(비루트)은 $\mathrm{low}[v] \ge \mathrm{disc}[u]$ . 이 하나를 헷갈리면 전부 틀린다.
루트 특수 처리: 루트는 lowlink 조건이 아니라 자식 수로 판정. 비루트 조건을 루트에 그대로 적용하면 루트를 항상 단절점으로 오판한다.
다중 간선(multi-edge): $$u,v$$ 사이 평행 간선이 2개면 그 사이는 다리가 아니다. "부모 정점"이 아니라 부모 간선 id로 역행을 막아야 이를 올바로 처리한다. 정점으로 막으면 평행 간선을 다리로 오판한다.
자기 루프(self-loop): 단절점·단절선 판정에 무의미하므로 무시하거나 애초에 제거. id == pe 검사가 자기 자신도 걸러 주도록 주의.
역간선 방향: else if (disc[v] < disc[u])로 위로 향하는 역간선만 처리·스택에 넣는다. 이 조건 없이 양방향을 다 넣으면 같은 간선을 두 번 세어 BCC가 깨진다.
비연결 그래프: 모든 정점에서 시작하는 외부 루프 필요. 각 연결 요소를 독립적으로 처리.
간선 스택 잔여: 한 연결 요소를 다 돌면 스택이 비어야 정상. 남으면 판정 조건이나 스택 push 위치가 잘못된 것.

정점 이중연결 vs 간선 이중연결

	제거 대상	요소 정의	축약 트리
단절점 / BCC	정점	간선 분할(단절점 공유)	블록-컷 트리
단절선 / 2-ECC	간선	정점 분할	다리 트리

두 개념을 섞지 말 것. "다리로 나뉘는 덩어리"(간선 관점)와 "단절점으로 나뉘는 블록"(정점 관점)은 서로 다른 분해다. 문제가 "정점을 못 쓰게 되면"인지 "간선(도로)이 끊기면"인지로 어느 쪽인지 판별한다.

Practice problem 단절선 선택 25m

R00391

단절선

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Practice problem 단절점 선택 25m

R00390

단절점

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Lesson 1강 · 개념과 존재 조건 — 모든 간선을 한 번씩 필수 8m

오일러 경로와 회로란

그래프의 모든 간선을 정확히 한 번씩 지나는 경로를 오일러 경로(Eulerian
path) 라 하고, 그런 경로가 출발점으로 되돌아오면(시작 정점 = 끝 정점)
오일러 회로(Eulerian circuit) 라 부릅니다. 흔히 말하는 "한붓그리기"가
바로 이것이며, 역사적으로는 오일러가 쾨니히스베르크의 일곱 다리 문제를 풀며
시작된 개념입니다. (정점을 한 번씩 지나는 해밀턴 경로와는 완전히 다른
문제입니다 — 아래 경고 참고.)

사용하는 대상: 정점이 아니라 간선입니다.
신호가 되는 표현: "모든 도로/다리/길을 한 번씩 지나라", "한붓그리기".

존재 조건 (가장 중요)

오일러 경로/회로는 존재 조건이 명확해서, 실제로 경로를 만들기 전에 먼저
"있는가?"를 차수만으로 판정할 수 있습니다.

무방향 그래프

간선이 있는 정점들이 하나의 연결 요소에 모두 속한다고 가정할 때:

대상	조건
오일러 회로	모든 정점의 차수가 짝수
오일러 경로	차수가 홀수인 정점이 정확히 0개 또는 2개

홀수 차수 정점이 2개면, 오일러 경로는 반드시 그 두 정점을 양 끝으로 합니다
(한 정점에서 출발해 다른 정점에서 끝남). 0개면 회로이므로 아무 정점에서
시작해도 됩니다. 홀수 정점이 4개, 6개 … 이면 한붓그리기는 불가능합니다.

직관: 지나가는 중간 정점은 "들어온 간선 1개 + 나가는 간선 1개"가 짝을 이루므로
차수가 짝수여야 하고, 짝이 맞지 않는(홀수) 정점은 오직 출발점과 도착점뿐입니다.

방향 그래프

대상	조건
오일러 회로	모든 정점에서 진입 차수 = 진출 차수 ( $\text{indeg}=\text{outdeg}$ )
오일러 경로	한 정점만 $\text{outdeg}-\text{indeg}=+1$ (시작), 한 정점만 $\text{indeg}-\text{outdeg}=+1$ (끝), 나머지는 모두 같음

방향 그래프에서는 추가로 간선을 무시했을 때 관련 정점들이 한 덩어리로
연결되어 있어야 합니다(정확히는 진출 차수가 있는 정점들이 강하게 하나로
이어져야 함).

작은 예제로 확인

정점 $\{1,2,3,4,5\}$ , 무방향 간선

$\{(1,2),(2,3),(3,1),(1,4),(4,5)\}$

차수를 세어 보면

정점	1	2	3	4	5
차수	3	2	2	2	1

홀수 차수 정점은 $$1$$ 과 $$5$$ 로 정확히 2개 → 오일러 경로가 존재하고, 그
경로는 $$5$$ 와 $$1$$ 을 양 끝으로 합니다. 실제로 한 가지 답은

$5 \to 4 \to 1 \to 3 \to 2 \to 1$

로, 다섯 개 간선을 모두 정확히 한 번씩 지납니다.

복잡도와 그래프 표현

존재 판정은 차수만 세면 되므로 $$O(V+E)$$ , 실제 경로 구성(다음 강의의 히어홀처
알고리즘)도 $$O(V+E)$$ 입니다. 구현에서는 인접 리스트에 간선 번호를 함께
저장하는 것이 핵심입니다 — 같은 간선을 두 번 쓰지 않도록 "사용 표시"를
간선 단위로 해야 하기 때문입니다.

해밀턴과 혼동하지 말 것

오일러(모든 간선 한 번) → 차수 조건으로 $$O(V+E)$$ 에 판정·구성. 쉬움.
해밀턴(모든 정점 한 번) → 일반 그래프에서 NP-난해. 완전히 다른
난이도입니다. 문제에서 "간선을 한 번씩"인지 "정점을 한 번씩"인지 반드시
구분하세요.

Lesson 2강 · 구현 — 히어홀처 알고리즘 선택 8m

히어홀처(Hierholzer) 알고리즘

존재 조건을 만족할 때 실제 경로를 만드는 표준 방법이 히어홀처 알고리즘
입니다. 아이디어는 "막다른 곳까지 계속 가다가, 더 갈 곳이 없으면 그 정점을
결과에 확정(뒤에서부터 쌓기)"하는 것입니다. 재귀로도 되지만 간선이 많으면
재귀 깊이가 폭발하므로 명시적 스택(반복) 구현을 권장합니다.

핵심 자료구조 두 가지:

각 정점마다 이터레이터 포인터 ptr[u] — 이미 살펴본 간선을 다시 보지
않게 해 전체를 $$O(V+E)$$ 로 유지합니다.
간선 사용 표시 used[] — 무방향 간선은 양방향으로 두 번 저장되므로,
간선 번호를 $$2k, 2k{+}1$$ 로 짝지어 한쪽을 쓰면 id와 id^1을 둘 다 사용
표시합니다.

C++ — 무방향 다중 그래프

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;                       // 정점 수, 간선 수
    vector<vector<pair<int,int>>> adj(n + 1);   // (이웃, 간선번호)
    vector<int> deg(n + 1, 0);
    for (int k = 0; k < m; k++) {
        int u, v; cin >> u >> v;
        adj[u].push_back({v, 2 * k});     // 간선 k의 두 방향: 2k, 2k+1
        adj[v].push_back({u, 2 * k + 1});
        deg[u]++; deg[v]++;
    }

    // 시작점: 홀수 차수 정점이 있으면 그곳, 없으면 간선이 달린 아무 정점
    int start = -1;
    for (int i = 1; i <= n; i++) if (deg[i]) { start = i; break; }
    for (int i = 1; i <= n; i++) if (deg[i] % 2) { start = i; break; }
    if (start == -1) { cout << "no edges\n"; return 0; }

    vector<int> ptr(n + 1, 0), used(2 * m, 0), st, path;
    st.push_back(start);
    while (!st.empty()) {
        int u = st.back();
        // 이미 쓴 간선은 건너뛴다
        while (ptr[u] < (int)adj[u].size() && used[adj[u][ptr[u]].second])
            ptr[u]++;
        if (ptr[u] == (int)adj[u].size()) {   // 더 갈 곳 없음 → 확정
            path.push_back(u);
            st.pop_back();
        } else {
            auto [v, id] = adj[u][ptr[u]++];
            used[id] = used[id ^ 1] = 1;      // 무방향: 양쪽 방향 모두 소모
            st.push_back(v);
        }
    }
    reverse(path.begin(), path.end());        // 결과는 거꾸로 쌓였다

    if ((int)path.size() != m + 1) {          // 모든 간선을 못 쓰면 = 불가능
        cout << -1 << '\n';
    } else {
        for (int x : path) cout << x << ' ';
        cout << '\n';
    }
}

path.size() == m + 1이 아니면(간선을 다 못 씀) 애초에 오일러 경로가 없는
그래프(홀수 정점 과다 또는 비연결)라는 뜻이므로 함께 판정할 수 있습니다.

Python

import sys
def hierholzer_undirected(n, edges):
    adj = [[] for _ in range(n + 1)]
    m = len(edges)
    deg = [0] * (n + 1)
    for k, (u, v) in enumerate(edges):
        adj[u].append((v, 2 * k))
        adj[v].append((u, 2 * k + 1))
        deg[u] += 1; deg[v] += 1
    used = [False] * (2 * m)

    start = next((i for i in range(1, n + 1) if deg[i]), -1)
    for i in range(1, n + 1):
        if deg[i] % 2:
            start = i; break
    if start == -1:
        return []

    ptr = [0] * (n + 1)
    st = [start]; path = []
    while st:
        u = st[-1]
        while ptr[u] < len(adj[u]) and used[adj[u][ptr[u]][1]]:
            ptr[u] += 1
        if ptr[u] == len(adj[u]):
            path.append(u); st.pop()
        else:
            v, eid = adj[u][ptr[u]]; ptr[u] += 1
            used[eid] = used[eid ^ 1] = True
            st.append(v)
    path.reverse()
    return path if len(path) == m + 1 else []   # 불가능하면 빈 리스트

print(hierholzer_undirected(5, [(1,2),(2,3),(3,1),(1,4),(4,5)]))
# -> [1, 2, 3, 1, 4, 5]  (모든 간선 한 번씩)

방향 그래프 버전

방향 그래프에서는 간선이 한 방향으로만 저장되므로 id^1 짝짓기가 필요 없고,
간선을 소모하면 그대로 ptr[u]만 넘기면 됩니다. 시작점은 $\text{outdeg} -
\text{indeg} = +1$인 정점(없으면 진출 간선이 있는 아무 정점)으로 잡습니다.

// 방향 그래프: adj[u]에 (v) 만 저장, ptr[u]로 소모
while (!st.empty()) {
    int u = st.back();
    if (ptr[u] < (int)adj[u].size()) {
        int v = adj[u][ptr[u]++];   // 간선 하나 소모
        st.push_back(v);
    } else {
        path.push_back(u);
        st.pop_back();
    }
}
reverse(path.begin(), path.end());

동작 추적 (앞 예제)

정점 $\{1..5\}$ , 간선 $\{(1,2),(2,3),(3,1),(1,4),(4,5)\}$ . 홀수 정점 $$1,5$$ 중
$$1$$ 에서 시작한다고 하면, 스택은 $1\to2\to3\to1\to4\to5$ 까지 뻗다가 $$5$$ 에서
막혀 확정이 시작되고, 되쌓아 뒤집으면 $1\,2\,3\,1\,4\,5$ — 다섯 간선을 모두
한 번씩 쓰는 오일러 경로가 나옵니다.

Lesson 3강 · 심화와 변형 — 함정, 사전순, 방향 그래프 선택 8m

자주 겪는 함정

재귀 깊이 폭발 — 간선이 수십만 개면 단순 재귀 히어홀처는 스택 오버플로가
납니다. 앞 강의처럼 명시적 스택(반복) 으로 구현하세요.
무방향 간선 사용 표시 — 무방향 간선은 인접 리스트에 두 번(양방향) 들어
갑니다. 간선 번호를 $2k,\,2k{+}1$ 로 짝지어 used[id]와 used[id ^ 1]을
동시에 표시하지 않으면 같은 간선을 두 번 쓰거나 무한 루프에 빠집니다.
ptr 포인터 없이 매번 처음부터 탐색 — while로 이미 쓴 간선을 건너뛰되,
포인터는 되돌리지 않습니다. 이 상각(amortized) 덕분에 전체가 $$O(V+E)$$ 가
됩니다. 매번 리스트를 처음부터 훑으면 $$O(VE)$$ 로 느려집니다.
연결성 확인 누락 — 차수 조건을 만족해도 간선이 여러 연결 요소로
흩어져 있으면 한붓그리기는 불가능합니다. 간선이 달린 정점들이 한 덩어리인지
확인하거나, 위 코드처럼 path.size() == m + 1로 사후 판정하세요.
자기 루프·다중 간선 — 오일러 이론은 다중 그래프에서도 그대로 성립합니다.
자기 루프는 차수에 2를 더한다는 점만 주의하면 됩니다. 인접 리스트 +
간선 번호 방식은 다중 간선도 자연히 처리합니다.
결과가 뒤집혀 있음 — 히어홀처는 막다른 정점부터 뒤에서 쌓으므로 마지막에
reverse 해야 올바른 순서입니다.

변형과 응용

사전순으로 가장 빠른 오일러 경로

여러 오일러 경로 중 사전순 최소를 요구하면, 각 정점의 인접 리스트를 정렬
하고(작은 이웃부터), 히어홀처를 그대로 돌리면 됩니다. 정렬된 인접 리스트를
ptr로 순서대로 소모하므로 자연히 사전순 최소 경로가 나옵니다. 자주 지우고
넣는다면 multiset/우선순위 구조로 관리합니다.

방향/무방향 혼합 판정 절차

문제를 만나면 다음 순서로 처리하면 안전합니다.

방향인지 무방향인지 확인한다.
차수(무방향) 또는 진입·진출 차수(방향)를 센다.
위 표의 회로/경로 조건으로 존재 여부와 시작점을 결정한다.
존재하면 히어홀처로 실제 경로를 구성한다.

홀수 정점을 짝지어 잇기 (중국인 우편배달부의 맛보기)

오일러 회로가 없을 때(홀수 정점이 많을 때) "간선을 최소로 덧대어
한붓그리기를 가능하게 하라"는 확장이 중국인 우편배달부 문제입니다. 이때는
홀수 정점들을 최소 비용으로 짝짓는 매칭이 필요해 난도가 크게 오릅니다.
기본 오일러 판정과는 별개의 주제이니, 문제가 "간선을 추가/중복 허용"을
말하는지 먼저 확인하세요.

정리

간선을 한 번씩 → 오일러. 정점을 한 번씩(해밀턴)과 혼동 금지.
존재는 차수 조건만으로 $$O(V+E)$$ 판정: 무방향은 홀수 정점 0/2개,
방향은 진입=진출(회로) 또는 $\pm 1$ 한 쌍(경로).
실제 경로는 히어홀처를 반복 스택으로 $$O(V+E)$$ 에, 무방향은 id^1
간선 짝짓기로 사용 표시.

Practice problem 방향 오일러 회로 선택 25m

R00394

방향 오일러 회로

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Practice problem 무방향 오일러 판정 선택 25m

R00393

무방향 오일러 판정

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Lesson 최대 유량과 최소 컷 정리 필수 8m

최대 유량 문제

용량이 정해진 방향 간선들로 이뤄진 네트워크에서, 소스 $$s$$ 에서 싱크 $$t$$ 로 흘려보낼 수 있는 흐름의 최댓값을 구한다. 각 간선 $$(u,v)$$ 에 용량 $c(u,v)\ge 0$ 이 있고, 흐름 $$f$$ 는

용량 제약: $0 \le f(u,v) \le c(u,v)$ ,
흐름 보존: $$s,t$$ 를 뺀 모든 정점에서 들어온 양 = 나간 양

을 만족해야 한다. 목표는 $$s$$ 에서 나가는 순 흐름 $$|f|$$ 를 최대화하는 것.

잔여 그래프와 증가 경로

핵심 도구는 잔여 그래프(residual graph) 다. 간선 $$(u,v)$$ 에 $$f$$ 만큼 흘렸다면 남은 용량은 $$c-f$$ 이고, 동시에 역방향 간선 $$(v,u)$$ 에 $$f$$ 만큼의 잔여 용량이 생긴다. 역방향 용량은 "이미 보낸 흐름을 되돌릴 수 있다"는 뜻이며, 잘못 배치된 흐름을 재조정하게 해 준다.

잔여 그래프에서 잔여 용량이 모두 양수인 $s\to t$ 경로가 증가 경로다. 경로상의 최소 잔여 용량만큼 흘리면 총 유량이 늘어난다. 증가 경로가 없을 때까지 반복하는 것이 포드–풀커슨 방법이다.

최대 유량 최소 컷 정리

컷이란 정점을 $$s$$ 쪽 $$S$$ 와 $$t$$ 쪽 $$T$$ 로 나누는 것이고, 그 용량은 $S\to T$ 로 가는 간선들의 용량 합이다.

정리 (Max-Flow Min-Cut). 최대 유량의 값 = 최소 컷의 용량.

증명 골자:
1. 약한 쌍대성: 임의의 흐름 $$|f|$$ 는 임의의 컷을 통과하므로 어떤 컷 용량도 넘을 수 없다. 따라서 $\max|f| \le \min\text{cut}$ .
2. 강한 쌍대성: 증가 경로가 더 없을 때, $$s$$ 에서 잔여 그래프로 도달 가능한 집합 $$S$$ 를 잡으면 $S\to T$ 의 모든 원래 간선은 포화( $$f=c$$ )이고 $T\to S$ 간선은 흐름 0이다. 즉 $$|f| =$$ 이 컷의 용량이라 등호가 성립.

이 정리로 "최대로 보낼 수 있는 양"과 "최소 비용으로 끊는 법"이 같은 값이 된다.

종료와 복잡도

정수 용량이면 매 증가가 유량을 $\ge 1$ 늘리므로 유한 종료. 경로 선택이 나쁘면 느리므로:

에드몬드–카프(BFS 최단 증가 경로): $$O(VE^2)$$ .
디닉(레벨 그래프 + blocking flow): $O(V^2\ E)$ . 단위 용량이면 $O(E\sqrt V)$ .

실전에서는 디닉이 사실상 표준이며 대부분의 문제에서 매우 빠르다.

무엇을 모델링하나

이분 매칭, 정점 용량, 간선/정점-서로소 경로 수, 프로젝트 선택(최대 가중 닫힌 집합), 이미지 분할 등 수많은 최적화가 최대 유량/최소 컷으로 환원된다. 모델링 능력이 이 주제의 진짜 핵심이다(3강).

Lesson 디닉 알고리즘 구현 선택 8m

디닉의 두 단계

디닉은 다음을 반복한다.

레벨 그래프: BFS로 $$s$$ 에서의 거리(레벨)를 매긴다. $$t$$ 에 도달 못 하면 종료.
blocking flow: 레벨이 정확히 1씩 증가하는 간선만 따라 DFS로 더 못 보낼 때까지 흐름을 밀어 넣는다.

레벨 단계가 최대 $$O(V)$$ 번, 각 blocking flow가 $$O(VE)$$ 라 전체 $$O(V^2E)$$ 다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

struct Dinic {
    struct Edge { int to; ll cap; int rev; };
    vector<vector<Edge>> g;
    vector<int> level, it;
    int n;
    Dinic(int n): g(n), level(n), it(n), n(n) {}

    void add_edge(int u, int v, ll c) {
        g[u].push_back({v, c, (int)g[v].size()});
        g[v].push_back({u, 0, (int)g[u].size() - 1});   // 역간선 용량 0
    }
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q; level[s] = 0; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto& e : g[u])
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[u] + 1; q.push(e.to);
                }
        }
        return level[t] >= 0;
    }
    ll dfs(int u, int t, ll f) {
        if (u == t) return f;
        for (int& i = it[u]; i < (int)g[u].size(); i++) {
            Edge& e = g[u][i];
            if (e.cap > 0 && level[u] + 1 == level[e.to]) {
                ll d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) { e.cap -= d; g[e.to][e.rev].cap += d; return d; }
            }
        }
        return 0;
    }
    ll max_flow(int s, int t) {
        ll flow = 0;
        while (bfs(s, t)) {
            fill(it.begin(), it.end(), 0);
            while (ll f = dfs(s, t, INF)) flow += f;
        }
        return flow;
    }
};

CLRS 표준 예제(정점 6개)에서 이 코드는 최대 유량 23을 반환한다.

Python (디닉)

from collections import deque

class Dinic:
    def __init__(self, n):
        self.n = n
        self.g = [[] for _ in range(n)]     # 각 원소: [to, cap, rev_index]
    def add_edge(self, u, v, c):
        self.g[u].append([v, c, len(self.g[v])])
        self.g[v].append([u, 0, len(self.g[u]) - 1])
    def bfs(self, s, t):
        self.level = [-1] * self.n
        q = deque([s]); self.level[s] = 0
        while q:
            u = q.popleft()
            for v, cap, _ in self.g[u]:
                if cap > 0 and self.level[v] < 0:
                    self.level[v] = self.level[u] + 1; q.append(v)
        return self.level[t] >= 0
    def dfs(self, u, t, f):
        if u == t: return f
        while self.it[u] < len(self.g[u]):
            e = self.g[u][self.it[u]]
            v, cap, rev = e
            if cap > 0 and self.level[u] + 1 == self.level[v]:
                d = self.dfs(v, t, min(f, cap))
                if d > 0:
                    e[1] -= d; self.g[v][rev][1] += d; return d
            self.it[u] += 1
        return 0
    def max_flow(self, s, t):
        flow = 0; INF = float('inf')
        while self.bfs(s, t):
            self.it = [0] * self.n
            while True:
                f = self.dfs(s, t, INF)
                if f == 0: break
                flow += f
        return flow

흔한 실수

역간선 용량: 일반 간선의 역간선은 용량 0으로 시작. 무방향 간선이면 양쪽 모두 용량 $$c$$ 로 두 개를 넣는다.
it(현재 간선 포인터): blocking flow마다 0으로 리셋하되, 한 BFS 단계 안에서는 막힌 간선을 다시 안 보도록 유지. 이 포인터가 없으면 복잡도가 무너진다.
오버플로: 용량 합이 크면 long long과 큰 INF 사용.

Lesson 심화: 정점분할·하한유량·최소컷 복원·모델링 선택 8m

모델링 패턴

문제	모델링
이분 매칭	$s\to$ 왼쪽(용량1), 왼쪽 $\to$ 오른쪽(용량1), 오른쪽 $\to t$ (용량1)
정점 용량 $$cap(v)$$	정점을 $v_{in}, v_{out}$ 로 쪼개고 $v_{in}\to v_{out}$ 에 용량 $$cap(v)$$
정점-서로소 경로 수	위 정점분할 + 각 정점 용량 1
간선-서로소 경로 수	각 간선 용량 1, 최대 유량
프로젝트 선택(최대 이익)	최대 이익 $= \sum(\text{양의 이익}) - \min\text{컷}$

정점 분할과 정점-서로소 경로

간선이 아니라 정점에 용량이 걸리거나(한 정점을 한 번만 통과), 정점-서로소 경로 개수를 셀 때는 각 정점 $$v$$ 를 $v_{in}\to v_{out}$ 간선(용량 = 정점 용량, 경로 세기면 1)으로 쪼갠다. 원래 간선 $$(u,v)$$ 는 $u_{out}\to v_{in}$ 이 된다. 메뉴에 나오는 대부분의 격자·미로 유량 문제가 이 기법을 요구한다.

하한(lower bound) 있는 유량

간선에 하한 $$l(u,v)$$ 과 상한 $$c(u,v)$$ 이 모두 있는 feasible flow는 다음으로 환원한다.

각 간선의 용량을 $$c-l$$ 로 바꾸고, 하한 $$l$$ 만큼은 "무조건 흐른다"고 간주.
초과/부족을 보정하는 슈퍼 소스 $$S'$$ , 슈퍼 싱크 $$T'$$ 추가: 정점 $$v$$ 의 (들어오는 하한 합 $$-$$ 나가는 하한 합) $$= d(v)$$ 가 양수면 $S'\to v$ (용량 $$d$$ ), 음수면 $v\to T'$ (용량 $$-d$$ ).
$t\to s$ 에 용량 $\infty$ 간선을 추가한 뒤 $S'\to T'$ 최대 유량을 구해, 모든 $$S'$$ 나가는 간선이 포화되면 실행 가능.
최소/최대 유량은 여기에 이분 탐색이나 잔여 그래프 추가 계산을 얹는다.

최소 컷 집합 복원

최대 유량 계산 후 마지막 잔여 그래프에서 $$s$$ 로부터 BFS로 도달 가능한 집합 $$S$$ 를 구한다. $$S$$ 에서 $$S$$ 밖으로 나가는 원래(정방향) 간선들이 최소 컷을 이룬다.

// max_flow 실행 후
vector<bool> inS(d.n, false);
queue<int> q; q.push(s); inS[s] = true;
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (auto& e : d.g[u]) if (e.cap > 0 && !inS[e.to]) { inS[e.to] = true; q.push(e.to); }
}
// inS[u] && !inS[v] 인 원래 간선 (u,v) 들이 최소 컷

프로젝트 선택 / 최대 가중 닫힌 집합

"선택하면 이익 $$p_i$$ 이지만 선행 프로젝트를 함께 선택해야 하는" 유형은 최소 컷으로 푼다. 이익 양수 노드는 $s\to i$ (용량 $$p_i$$ ), 손실 노드는 $i\to t$ (용량 $$|p_i|$$ ), 의존 관계 $$i$$ 가 $$j$$ 를 요구하면 $i\to j$ (용량 $\infty$ ). 답 $= \sum_{p_i>0} p_i - \min\text{컷}$ . $\infty$ 간선이 의존성을 어기는 선택을 막는다.

엣지 케이스·버그

무방향 간선: 양방향 용량 $$c$$ 두 개. 역간선 0으로 두면 방향 간선이 되어 틀린다.
다중 간선/자기 루프: 다중 간선은 그냥 여러 번 추가하면 되고, 자기 루프는 유량에 무의미하므로 무시.
큰 $\infty$ : 의존성용 $\infty$ 간선은 실제 용량 합보다 크되 오버플로하지 않게(예: $10^{18}$ ) 설정.
디닉의 종료: 정수 용량 가정. 실수 용량이면 종료 보장이 약해지므로 정수화하거나 반복 상한을 둔다.

네트워크 플로우는 이어지는 이분 매칭, MCMF, 고모리–후 트리의 토대다. 모델링 사전을 늘리는 것이 실력의 관건이다.

Practice problem 도시의 모든 절단면 선택 25m

R00676

도시의 모든 절단면

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Practice problem 네트워크 최소 절단 선택 25m

R00656

네트워크 최소 절단

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Lesson 증가 경로·쾨니그·홀 정리 필수 8m

이분 매칭 문제

정점이 두 집합 $$L, R$$ 로 나뉘고 간선이 항상 $$L$$ – $$R$$ 사이에만 있는 이분 그래프에서, 서로 정점을 공유하지 않는 간선들의 집합을 매칭(matching) 이라 한다. 최대 매칭은 간선 수가 최대인 매칭이다.

작업–일꾼 배정, 좌–우 대응, 격자 도미노 덮기, 행–열 선택 등 "서로 겹치지 않게 짝짓기"가 필요한 곳에 쓴다.

증가 경로 정리

매칭 $$M$$ 에 대해, 매칭 안 된 정점에서 시작해 비매칭–매칭 간선이 번갈아 나오며 매칭 안 된 정점에서 끝나는 경로를 증가 경로(augmenting path) 라 한다. 이 경로 위에서 매칭/비매칭을 뒤집으면 매칭 크기가 정확히 1 늘어난다.

베르주 정리. 매칭 $$M$$ 이 최대 $\iff$ $$M$$ 에 대한 증가 경로가 존재하지 않는다.

그래서 알고리즘은 단순하다: 증가 경로를 하나씩 찾아 뒤집기를 반복. 이분 그래프에서는 홀수 사이클이 없어 증가 경로 탐색이 단순 DFS/BFS로 충분하다(일반 그래프는 홀수 사이클=블로섬 때문에 복잡해진다 → 일반 매칭 강의).

쾨니그 정리와 쌍대성

이분 매칭의 진짜 힘은 여러 조합량과의 동치에 있다.

쾨니그(König) 정리. 이분 그래프에서 최대 매칭의 크기 = 최소 정점 덮개(minimum vertex cover)의 크기.

정점 덮개란 모든 간선의 양 끝 중 적어도 하나를 포함하는 정점 집합이다. 또한 여집합 논리로:

최대 독립 집합(maximum independent set) 크기 $$= |V| - $$ 최대 매칭, 최소 간선 덮개 $$= |V| - $$ 최대 매칭(고립점 없을 때).

또 홀(Hall)의 결혼 정리: $$L$$ 을 모두 매칭할 수 있음 $\iff$ 임의의 $S\subseteq L$ 에 대해 $|N(S)| \ge |S|$ .

복잡도

쿤(Kuhn) 증가 경로법: $O(V\cdot E)$ .
홉크로프트–카프(Hopcroft–Karp): 여러 증가 경로를 동시에 찾아 $O(E\sqrt V)$ . 큰 그래프에서 훨씬 빠르다.

작은 예제

$L=\{0,1,2\}$ , $R=\{0,1,2\}$ , 간선 $0\!-\!0,\ 0\!-\!1,\ 1\!-\!0,\ 2\!-\!2$ .

처음 $0\!-\!0$ 매칭. 다음 $$1$$ 을 매칭하려 하면 $1\!-\!0$ 의 $$R_0$$ 이 이미 $$L_0$$ 과 매칭 → $$L_0$$ 을 $$R_1$$ 로 재배치(증가 경로 $1\!-\!0\!=\!0\!-\!1$ ) → $L_1\!-\!R_0$ , $L_0\!-\!R_1$ . 마지막 $2\!-\!2$ .
최대 매칭 = 3. 쾨니그에 의해 최소 정점 덮개도 3.

Lesson 쿤과 홉크로프트–카프 구현 선택 8m

쿤 알고리즘 (C++)

각 왼쪽 정점에 대해 DFS로 증가 경로를 찾는다. used(오른쪽 방문 표시)는 각 왼쪽 정점마다 초기화한다.

#include <bits/stdc++.h>
using namespace std;

int nL, nR;
vector<vector<int>> adj;         // adj[u] = u와 이어진 오른쪽 정점들
vector<int> matchR;             // matchR[v] = v와 매칭된 왼쪽 정점 (-1이면 없음)
vector<bool> used;

bool tryKuhn(int u) {
    for (int v : adj[u]) if (!used[v]) {
        used[v] = true;
        if (matchR[v] < 0 || tryKuhn(matchR[v])) {
            matchR[v] = u;
            return true;
        }
    }
    return false;
}

int maxMatching() {
    matchR.assign(nR, -1);
    int res = 0;
    for (int u = 0; u < nL; u++) {
        used.assign(nR, false);
        if (tryKuhn(u)) res++;
    }
    return res;
}

최적화 팁: 왼쪽 매칭 배열 matchL도 두고, 먼저 탐욕적으로 짝지어 초기 매칭을 만든 뒤 남은 정점만 DFS하면 상수가 크게 준다.

홉크로프트–카프 (C++)

BFS로 여러 증가 경로의 레벨 그래프를 만들고, DFS로 정점-서로소 증가 경로들을 한꺼번에 뒤집는다. $O(E\sqrt V)$ .

struct HopcroftKarp {
    int nL, nR;
    vector<vector<int>> adj;
    vector<int> dist, matchL, matchR;
    const int INF = 1e9;
    HopcroftKarp(int L, int R): nL(L), nR(R), adj(L), matchL(L, -1), matchR(R, -1) {}
    void addEdge(int u, int v){ adj[u].push_back(v); }
    bool bfs() {
        queue<int> q; dist.assign(nL, INF);
        for (int u = 0; u < nL; u++) if (matchL[u] < 0) { dist[u] = 0; q.push(u); }
        bool found = false;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                int w = matchR[v];
                if (w < 0) found = true;
                else if (dist[w] == INF) { dist[w] = dist[u] + 1; q.push(w); }
            }
        }
        return found;
    }
    bool dfs(int u) {
        for (int v : adj[u]) {
            int w = matchR[v];
            if (w < 0 || (dist[w] == dist[u] + 1 && dfs(w))) {
                matchL[u] = v; matchR[v] = u; return true;
            }
        }
        dist[u] = INF; return false;
    }
    int maxMatching() {
        int res = 0;
        while (bfs())
            for (int u = 0; u < nL; u++)
                if (matchL[u] < 0 && dfs(u)) res++;
        return res;
    }
};

두 코드 모두 위 예제에서 매칭 크기 3을 반환한다.

Python (쿤)

import sys
sys.setrecursionlimit(1 << 20)

def max_matching(nL, nR, adj):
    matchR = [-1] * nR
    def try_kuhn(u, used):
        for v in adj[u]:
            if not used[v]:
                used[v] = True
                if matchR[v] < 0 or try_kuhn(matchR[v], used):
                    matchR[v] = u
                    return True
        return False
    res = 0
    for u in range(nL):
        if try_kuhn(u, [False] * nR):
            res += 1
    return res, matchR

작은 그래프엔 쿤이 간단해 좋고, $$V,E$$ 가 크면(수만 이상) 홉크로프트–카프가 필수다.

Lesson 심화: 정점 덮개 복원·경로 덮개·모델링 선택 8m

최소 정점 덮개 복원 (쾨니그의 구성적 증명)

크기뿐 아니라 실제 최소 정점 덮개가 필요할 때가 많다. 최대 매칭 $$M$$ 을 구한 뒤:

$$L$$ 의 비매칭 정점 집합 $$U$$ 에서 시작.
교대 경로(비매칭 간선으로 $L\to R$ , 매칭 간선으로 $R\to L$ )를 따라 도달 가능한 정점 집합 $$Z$$ 를 구함.
최소 정점 덮개 $= (L \setminus Z) \cup (R \cap Z)$ .

이 집합의 크기가 정확히 $$|M|$$ 임이 쾨니그 정리의 구성적 증명이다. 최대 독립 집합은 그 여집합 $(L\cap Z)\cup(R\setminus Z)$ .

// matchL, matchR (쿤/HK 결과), adj 가 있다고 가정
vector<bool> visL(nL,false), visR(nR,false);
function<void(int)> dfs = [&](int u){
    visL[u]=true;
    for(int v:adj[u]) if(matchL[u]!=v && !visR[v]){  // 비매칭 간선으로 전진
        visR[v]=true;
        if(matchR[v]>=0 && !visL[matchR[v]]) dfs(matchR[v]); // 매칭 간선으로 복귀
    }
};
for(int u=0;u<nL;u++) if(matchL[u]<0) dfs(u);
// 최소 정점 덮개: L 중 미방문 + R 중 방문
vector<int> coverL, coverR;
for(int u=0;u<nL;u++) if(!visL[u]) coverL.push_back(u);
for(int v=0;v<nR;v++) if( visR[v]) coverR.push_back(v);

DAG 최소 경로 덮개

DAG의 정점들을 최소 개수의 정점-서로소 경로로 덮기는 이분 매칭으로 푼다. 각 정점 $$v$$ 를 좌측 $v_{\text{out}}$ , 우측 $v_{\text{in}}$ 으로 분할하고, DAG의 간선 $u\to v$ 마다 $u_{\text{out}}\!-\!v_{\text{in}}$ 을 넣는다.

$\text{최소 경로 덮개 수} = n - (\text{최대 이분 매칭}).$

매칭된 간선 하나가 두 정점을 한 경로로 잇기 때문이다. (경로가 정점을 공유해도 되는 변형은 도달성 폐포를 먼저 취한다.)

모델링 패턴과 함정

격자/도미노: 체스판처럼 칸을 흑백으로 2색칠하면 인접 칸은 항상 색이 다르므로 이분 그래프. 도미노 최대 배치 = 최대 매칭.
행–열, 좌표 대응: 왼쪽=행, 오른쪽=열 식으로 자연스럽게 이분.
최소 정점 덮개 / 최대 독립 집합: 일반 그래프에선 NP-난해지만 이분 그래프면 쾨니그로 다항 시간. 문제가 이분 구조인지부터 확인하라.

흔한 버그:

used 초기화 위치: 쿤에서 used는 왼쪽 정점 하나를 처리할 때마다 리셋. 전체를 한 번만 리셋하면 증가 경로를 못 찾아 매칭이 과소 계산된다.
양쪽 매칭 배열 동기화: 재배치 시 matchL과 matchR을 둘 다 갱신. 한쪽만 바꾸면 다음 DFS가 꼬인다.
간선 방향 착각: 그래프가 정말 이분인지(홀수 사이클 없는지) 확인. 이분이 아니면 쿤/HK는 최대 매칭을 보장하지 못한다 → 블로섬(일반 매칭) 필요.
정점 번호 충돌: $$L$$ 과 $$R$$ 의 정점 번호 공간을 분리(또는 위 코드처럼 별도 배열)해야 한다.
복원 시 재방문 방지: 최소 덮개 복원 DFS에서 방문 표시(visL/visR)를 정확히 관리하지 않으면 무한 루프.

Practice problem 결투의 짝짓기 선택 25m

R00695

결투의 짝짓기

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

다이아몬드 II 지금 풀기

Practice problem 감시 카메라 최소 설치 선택 25m

R00603

감시 카메라 최소 설치

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Level 6 · Strategist

Strategist

그래프 이론 · Strategist 단계

0/5 완료

Lesson 비용까지 최적인 유량: 이론 필수 8m

비용까지 최적인 유량

각 간선에 용량 $$c(u,v)$$ 뿐 아니라 단위 흐름당 비용 $$w(u,v)$$ 가 붙는다. 흐름 $$f$$ 의 총비용은 $\sum_{(u,v)} f(u,v)\,w(u,v)$ . 최소 비용 최대 유량(MCMF) 은 (1) 유량을 최대로 하되, (2) 그중 총비용이 최소인 흐름을 찾는다. 변형으로 "정확히 유량 $$k$$ 를 최소 비용으로", "비용이 음수가 되기 전까지 최대 이익" 등이 있다.

작업 배정(비용 최소), 운송 문제, k-경로 최소합, 이분 그래프 최소 비용 완전 매칭 등에 쓴다.

최단 비용 증가 경로 원리

MCMF의 뼈대는 최대 유량과 같되, 증가 경로를 아무거나가 아니라 비용이 최소인 경로로 고른다는 점이다. 잔여 그래프에서 역간선의 비용은 $$-w$$ 로 둔다(흐름을 되돌리면 비용도 되돌아오므로).

정리. 매 단계 현재 잔여 그래프에서 비용 최소 $s\to t$ 경로로 증가시키면, 각 유량 값에서 항상 그 값 대비 최소 비용 흐름을 유지한다.

증명 아이디어: 최소 비용 흐름 $$f$$ 의 잔여 그래프에는 음수 비용 사이클이 없다(있으면 그 사이클로 돌려 비용을 더 낮출 수 있어 최소성에 모순). 최소 비용 경로로 증가시켜도 이 무음수사이클 불변식이 유지되고, 그 증가량은 "다음 유량 값의 최소 비용"이 됨을 보일 수 있다. 따라서 유량 1씩(또는 병목만큼) 늘리며 항상 최적을 유지한다.

왜 잠재값(potential)인가

역간선 때문에 잔여 그래프에는 음수 비용 간선이 생긴다. 그래서 단순 다익스트라를 못 쓰고 SPFA/벨만–포드가 필요하다. 하지만 존슨 잠재값(potential) $$h[v]$$ (초기엔 최단 비용)를 두고 간선 비용을 $$w'(u,v)=w(u,v)+h[u]-h[v]$$ 로 바꾸면 모든 간선이 비음수가 되어 다익스트라를 쓸 수 있다. 매 증가 후 $h[v] \mathrel{+}= \text{dist}[v]$ 로 갱신한다.

복잡도

SPFA 기반: 최악 $O(V\cdot E)$ per 증가 × 증가 횟수. 랜덤/실전에선 빠르지만 최악이 나쁠 수 있다.
다익스트라+잠재값: 증가마다 $O(E\log V)$ . 증가 횟수를 $$F$$ (유량 또는 경로 수)라 하면 $O(F\cdot E\log V)$ . 큰 비용 그래프에서 안정적.

작은 예제

$$s=0,t=3$$ . 간선 $0\!\to\!1$ (용량2,비용1), $1\!\to\!3$ (용량2,비용1), $0\!\to\!2$ (용량2,비용5), $2\!\to\!3$ (용량2,비용5).

먼저 싼 경로 $0\!-\!1\!-\!3$ (단위비용 2)로 2만큼 → 비용 4.
남은 유량은 비싼 $0\!-\!2\!-\!3$ (단위비용 10)로 2만큼 → 비용 20.
최대 유량 4, 최소 비용 24. 순서를 바꿔 비싼 경로부터 흘리면 총비용이 커진다 — "매번 최단 비용 경로"가 최적을 보장한다.

Lesson SPFA·다익스트라+잠재값 구현 선택 8m

SPFA 기반 MCMF (C++)

가장 흔한 형태. 음수 비용(역간선)을 허용하는 SPFA로 최단 비용 경로를 찾고 병목만큼 흘린다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

struct MCMF {
    struct Edge { int to; ll cap, cost; int rev; };
    vector<vector<Edge>> g;
    int n;
    vector<ll> dist;
    vector<int> pv, pe;
    vector<bool> inq;
    MCMF(int n): g(n), n(n) {}

    void add_edge(int u, int v, ll cap, ll cost) {
        g[u].push_back({v, cap,  cost, (int)g[v].size()});
        g[v].push_back({u, 0,   -cost, (int)g[u].size() - 1});  // 역간선: 용량0, 비용 -cost
    }
    bool spfa(int s, int t) {
        dist.assign(n, INF); pv.assign(n, -1); pe.assign(n, -1); inq.assign(n, false);
        deque<int> q; dist[s] = 0; q.push_back(s);
        while (!q.empty()) {
            int u = q.front(); q.pop_front(); inq[u] = false;
            for (int i = 0; i < (int)g[u].size(); i++) {
                auto& e = g[u][i];
                if (e.cap > 0 && dist[u] + e.cost < dist[e.to]) {
                    dist[e.to] = dist[u] + e.cost; pv[e.to] = u; pe[e.to] = i;
                    if (!inq[e.to]) { inq[e.to] = true; q.push_back(e.to); }
                }
            }
        }
        return dist[t] < INF;
    }
    pair<ll,ll> run(int s, int t) {        // {최대 유량, 최소 비용}
        ll flow = 0, cost = 0;
        while (spfa(s, t)) {
            ll f = INF;
            for (int v = t; v != s; v = pv[v]) f = min(f, g[pv[v]][pe[v]].cap);
            for (int v = t; v != s; v = pv[v]) {
                auto& e = g[pv[v]][pe[v]];
                e.cap -= f; g[v][e.rev].cap += f;
            }
            flow += f; cost += f * dist[t];
        }
        return {flow, cost};
    }
};

위 예제에서 run(0,3)은 {4, 24}를 반환한다.

다익스트라 + 잠재값 (C++)

증가 횟수가 많거나 비용이 커서 SPFA가 불안하면 이쪽. 초기 잠재값은 벨만–포드로 잡아 최초의 음수 간선까지 처리한다(원 간선 비용이 비음수면 초기 $$h=0$$ 으로 충분).

struct MCMF_Dijkstra {
    struct Edge { int to; ll cap, cost; int rev; };
    vector<vector<Edge>> g; int n;
    vector<ll> h, dist; vector<int> pv, pe;
    MCMF_Dijkstra(int n): g(n), n(n), h(n, 0) {}
    void add_edge(int u, int v, ll cap, ll cost) {
        g[u].push_back({v, cap, cost, (int)g[v].size()});
        g[v].push_back({u, 0, -cost, (int)g[u].size() - 1});
    }
    pair<ll,ll> run(int s, int t) {
        ll flow = 0, cost = 0;
        // 초기 잠재값: 음수 간선이 있으면 벨만-포드로
        h.assign(n, INF); h[s] = 0;
        for (int i = 0; i < n - 1; i++)
            for (int u = 0; u < n; u++) if (h[u] < INF)
                for (auto& e : g[u]) if (e.cap > 0 && h[u] + e.cost < h[e.to])
                    h[e.to] = h[u] + e.cost;
        for (int i = 0; i < n; i++) if (h[i] == INF) h[i] = 0;
        while (true) {
            dist.assign(n, INF); pv.assign(n, -1); pe.assign(n, -1);
            priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
            dist[s] = 0; pq.push({0, s});
            while (!pq.empty()) {
                auto [d, u] = pq.top(); pq.pop();
                if (d > dist[u]) continue;
                for (int i = 0; i < (int)g[u].size(); i++) {
                    auto& e = g[u][i];
                    if (e.cap > 0) {
                        ll nd = dist[u] + e.cost + h[u] - h[e.to];   // 감소 비용
                        if (nd < dist[e.to]) { dist[e.to] = nd; pv[e.to] = u; pe[e.to] = i; pq.push({nd, e.to}); }
                    }
                }
            }
            if (dist[t] == INF) break;
            for (int i = 0; i < n; i++) if (dist[i] < INF) h[i] += dist[i];
            ll f = INF;
            for (int v = t; v != s; v = pv[v]) f = min(f, g[pv[v]][pe[v]].cap);
            for (int v = t; v != s; v = pv[v]) { auto& e = g[pv[v]][pe[v]]; e.cap -= f; g[v][e.rev].cap += f; }
            flow += f; cost += f * (h[t] - h[s]);      // h[t]가 실제 최단 비용
        }
        return {flow, cost};
    }
};

두 구현 모두 예제에서 {4, 24}를 준다. add_edge의 역간선 비용 부호( $$-cost$$ )와 잠재값 갱신이 정확성의 핵심이다.

Lesson 심화: 유량 k·볼록 비용·모델링·함정 선택 8m

변형과 모델링

유량 $$k$$ 의 최소 비용

"최대"가 아니라 정확히 $$k$$ 만큼 최소 비용으로 보내려면, 증가 루프에서 남은 목표 $$k$$ 를 추적해 병목을 $\min(f, k_{\text{남음}})$ 으로 자르고 $$k$$ 를 다 채우면 멈춘다. 도달 불가면 $$k$$ 를 못 채운 것.

최대 이익(음수 비용에서 정지)

"비용이 곧 손해"이고 이득이 나는 동안만 흘리고 싶으면, 최단 비용 경로의 비용이 0 이상이 되는 순간 중단한다(그 이후 증가는 총이익을 깎으므로). 최소 비용 최대 유량과 최대 이익 유량은 다르다 — 문제 요구를 정확히 읽어야 한다.

볼록 비용

한 간선의 흐름이 늘수록 단위 비용이 커지는 볼록 비용 함수는, 그 간선을 "용량 1·비용 $w_1 \le w_2 \le \dots$ " 인 여러 평행 간선으로 쪼개면 된다. MCMF가 항상 싼 조각부터 쓰므로 볼록성이 보장된다(오목이면 이 분해가 틀림).

최소 비용 완전(이분) 매칭

좌–우 매칭에 비용이 붙은 할당 문제는 $s\to$ 좌(용량1,비용0), 좌 $\to$ 우(용량1,비용=할당비용), 우 $\to t$ (용량1,비용0)로 MCMF. $n\times n$ 완전 매칭이면 헝가리안 알고리즘( $$O(n^3)$$ )이 대개 더 빠르다(헝가리안 강의 참고).

초기 음수 간선 처리

원래 간선에 음수 비용이 있으면(예: 이익을 음수 비용으로 표현) 다익스트라의 초기 잠재값을 반드시 벨만–포드로 잡아야 한다. 음수 사이클이 원 그래프에 있으면 MCMF 자체가 정의되지 않으니, 그런 모델링은 피하거나 상수를 더해 비음수화한다.

엣지 케이스와 흔한 버그

역간선 비용 부호: 반드시 $-\text{cost}$ . 이걸 $+\text{cost}$ 로 두면 흐름 되돌림 비용이 틀려 답이 어긋난다.
잠재값 갱신 누락: 다익스트라판에서 매 증가 후 $h[v]\mathrel{+}=\text{dist}[v]$ 를 빼먹으면 다음 라운드에서 음수 간선이 되살아나 다익스트라가 틀린다. 도달 못 한 정점( $\text{dist}=\infty$ )의 $$h$$ 는 건드리지 않는다.
비용 누적: SPFA판은 cost += f * dist[t], 다익스트라판은 cost += f * (h[t]-h[s]). 감소 비용을 그대로 곱하면 안 된다(잠재값을 되더해 실제 비용으로).
오버플로: 유량 × 비용이 커질 수 있으니 long long. INF는 충분히 크게.
SPFA 최악: 격자형·특수 그래프에서 SPFA가 지수적으로 느려질 수 있다. 시간 초과 시 다익스트라+잠재값으로 교체.
여러 최단 경로: 같은 비용의 경로가 많으면 어느 것을 골라도 총비용은 같다. 유량이 병목만큼 한꺼번에 흐르도록 병목 계산을 정확히.

MCMF는 최대 유량 위에 "최단 비용 경로 선택"을 얹은 것이다. 디닉(네트워크 플로우)과 최단 경로(SPFA/다익스트라) 둘 다 탄탄해야 디버깅이 쉽다.

Practice problem 용량 있는 작업 분담 선택 25m

R00421

용량 있는 작업 분담

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Practice problem 일꾼 배정과 최소 비용 선택 25m

R00420

일꾼 배정과 최소 비용

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Level 8 · Expert

Expert

그래프 이론 · Expert 단계

0/4 완료

Lesson 할당 문제와 LP 쌍대성 필수 8m

할당 문제

$$n$$ 명의 일꾼과 $$n$$ 개의 작업, 일꾼 $$i$$ 가 작업 $$j$$ 를 맡을 때 비용 $a_{ij}$ . 각 일꾼이 서로 다른 작업 하나씩을 맡도록 하는 완전 매칭 중 총비용이 최소인 것을 찾는 문제가 할당 문제(assignment problem) 다. 즉 순열 $\sigma$ 에 대해

$\min_{\sigma}\ \sum_{i=1}^{n} a_{i,\sigma(i)}.$

모든 순열을 시도하면 $$n!$$ 이지만, 헝가리안 알고리즘(쿤–문크레스) 은 $$O(n^3)$$ 에 최적해를 준다.

LP 쌍대성과 잠재값

할당 문제는 정수 선형계획이지만 제약 행렬이 완전 유니모듈러라 LP 완화가 정수 최적을 준다. 그 쌍대(dual) 는 각 행 $$i$$ 에 잠재값 $$u_i$$ , 각 열 $$j$$ 에 $$v_j$$ 를 두고

$\max\ \sum_i u_i + \sum_j v_j \quad\text{s.t.}\quad u_i + v_j \le a_{ij}\ \ \forall i,j.$

상보적 여유(complementary slackness). 원문제 최적 매칭 $\sigma$ 와 쌍대 최적 $$(u,v)$$ 는 매칭에 쓰인 간선에서 여유가 0이다: $u_i + v_{\sigma(i)} = a_{i,\sigma(i)}$ .

즉 " $u_i+v_j = a_{ij}$ 인 빡빡한(tight) 간선"만으로 완전 매칭을 만들 수 있으면 그것이 최적이다. 헝가리안은 잠재값 $$u,v$$ 를 유지하며 빡빡한 간선의 이분 그래프에서 매칭을 키우고, 막히면 잠재값을 조정해 새 빡빡한 간선을 만든다. 총비용은 쌍대값의 합 $\sum u_i + \sum v_j$ 와 같다.

언제 쓰나

$n\times n$ (또는 잘라서 정사각으로 만들 수 있는) 완전 매칭 최소/최대 비용.
밀집(dense) 비용 행렬: 헝가리안 $$O(n^3)$$ 이 MCMF보다 상수·구현 모두 유리.
사진 대응, 트래킹, 스케줄 배정, 최소합 순열 등.

간선이 희소하고 완전 매칭이 아니어도 되면 오히려 MCMF가 나을 수 있다.

작은 예제

비용 행렬(행=일꾼, 열=작업):

$\begin{pmatrix} 4 & 1 & 3 \\ 2 & 0 & 5 \\ 3 & 2 & 2 \end{pmatrix}$

일꾼1→작업2(비용 1), 일꾼2→작업1(비용 2), 일꾼3→작업3(비용 2).
총비용 $$1+2+2 = 5$$ , 이것이 최소(모든 $$3! = 6$$ 순열 중 최솟값).

헝가리안은 이 배정과 비용 5를, 쌍대 잠재값을 조정해 가며 $$O(n^3)$$ 에 찾는다.

Lesson $O(n^3)$ 구현 선택 8m

$$O(n^3)$$ 구현 (C++)

널리 쓰이는 e-maxx 형태다. 1-인덱스로, a[1..n][1..m]( $n\le m$ )의 최소 비용 매칭을 구한다. 열마다 잠재값 v, 행마다 u, p[j]는 열 $$j$$ 에 매칭된 행, way[j]는 증가 경로 복원용이다. 한 행씩 추가하며 최단 증가 경로를 다익스트라식으로 확장한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

// a: 1..n 행, 1..m 열 (n <= m). 반환: 최소 총비용, ans[i] = 행 i가 맡은 열
ll hungarian(vector<vector<ll>>& a, int n, int m, vector<int>& ans) {
    vector<ll> u(n + 1), v(m + 1);
    vector<int> p(m + 1), way(m + 1);
    for (int i = 1; i <= n; i++) {
        p[0] = i;
        int j0 = 0;                       // 현재 미매칭 열 (0은 가상 시작)
        vector<ll> minv(m + 1, INF);
        vector<char> used(m + 1, false);
        do {
            used[j0] = true;
            int i0 = p[j0], j1 = -1;
            ll delta = INF;
            for (int j = 1; j <= m; j++) if (!used[j]) {
                ll cur = a[i0][j] - u[i0] - v[j];      // 감소 비용(여유)
                if (cur < minv[j]) { minv[j] = cur; way[j] = j0; }
                if (minv[j] < delta) { delta = minv[j]; j1 = j; }
            }
            for (int j = 0; j <= m; j++) {
                if (used[j]) { u[p[j]] += delta; v[j] -= delta; }
                else minv[j] -= delta;
            }
            j0 = j1;
        } while (p[j0] != 0);
        do {                                            // 증가 경로 복원
            int j1 = way[j0]; p[j0] = p[j1]; j0 = j1;
        } while (j0);
    }
    ans.assign(n + 1, -1);
    for (int j = 1; j <= m; j++) if (p[j]) ans[p[j]] = j;
    return -v[0];                                       // 총 최소 비용
}

3×3 예제에서 이 코드는 비용 5, 배정 (1→2, 2→1, 3→3)을 반환하며 완전탐색 결과와 일치한다.

Python

$$n$$ 이 수백 정도면 파이썬으로도 충분하다.

INF = float('inf')

def hungarian(a, n, m):        # a: 1-indexed (a[0]/열0 은 미사용), n <= m
    u = [0] * (n + 1); v = [0] * (m + 1)
    p = [0] * (m + 1); way = [0] * (m + 1)
    for i in range(1, n + 1):
        p[0] = i; j0 = 0
        minv = [INF] * (m + 1); used = [False] * (m + 1)
        while True:
            used[j0] = True
            i0 = p[j0]; delta = INF; j1 = -1
            for j in range(1, m + 1):
                if not used[j]:
                    cur = a[i0][j] - u[i0] - v[j]
                    if cur < minv[j]:
                        minv[j] = cur; way[j] = j0
                    if minv[j] < delta:
                        delta = minv[j]; j1 = j
            for j in range(m + 1):
                if used[j]:
                    u[p[j]] += delta; v[j] -= delta
                else:
                    minv[j] -= delta
            j0 = j1
            if p[j0] == 0:
                break
        while j0:
            j1 = way[j0]; p[j0] = p[j1]; j0 = j1
    ans = [-1] * (n + 1)
    for j in range(1, m + 1):
        if p[j]:
            ans[p[j]] = j
    return -v[0], ans

정확성의 핵심

delta는 미방문 열들의 최소 여유이며, 이만큼 잠재값을 밀어 새 빡빡한 간선을 만든다.
used[j]인 열의 행 잠재값 $$u$$ 는 $+\delta$ , 열 잠재값 $$v$$ 는 $-\delta$ , 미방문 열의 minv는 $-\delta$ — 이 세 갱신이 상보적 여유를 보존한다.
반환값은 $$-v_0$$ : 가상 열 0에 누적된 값이 곧 총비용이 되도록 설계돼 있다.

Lesson 심화: 최대화·직사각·금지·MCMF 비교 선택 8m

최대화·직사각·희소 변형

최대화

"이익을 최대화"하려면 모든 비용을 부호 반전( $a_{ij} \to -a_{ij}$ ) 또는 큰 상수 $$C$$ 에서 빼서( $C - a_{ij}$ ) 최소화로 바꾼다. 부호 반전이 가장 간단.

직사각(일꾼 ≠ 작업 수)

$n \ne m$ 이면 부족한 쪽을 더미 행/열(비용 0 또는 상황에 맞는 값)로 채워 정사각으로 만든다. 위 구현은 $n \le m$ 인 직사각을 직접 지원하지만, "모든 일꾼을 반드시 배정" 같은 요구가 있으면 더미 비용 설정에 주의.

일부만 배정(부분 할당)

"최대 $$k$$ 명만 배정, 나머지는 안 해도 됨"은 더미 작업(비용 0)을 $$n-k$$ 개 추가하거나 MCMF로 유량 상한을 두는 편이 명확하다.

금지된 배정

일꾼 $$i$$ 가 작업 $$j$$ 를 못 맡으면 $a_{ij} = +\infty$ (충분히 큰 값)로 둔다. 단, 총합 오버플로와 " $\infty$ 가 최적해에 섞이는" 경우(실행 불가능)를 구분해야 한다.

헝가리안 vs MCMF

상황	권장
$n\times n$ 밀집 완전 매칭	헝가리안 $$O(n^3)$$
희소 이분 그래프, 완전 매칭 아님	MCMF
정점/간선 용량 등 일반 제약	MCMF
매우 큰 $$n$$ 이지만 특수 구조	문제별

할당 문제는 최소 비용 완전 이분 매칭의 특수형이므로 MCMF로도 정확히 풀린다. 헝가리안은 그 특수형에 최적화된 상수·메모리 이점이 있을 뿐, 답은 같다.

엣지 케이스·흔한 버그

인덱싱: 이 구현은 1-인덱스이고 열 0을 가상 시작으로 쓴다. 0-인덱스로 바꾸려다 오프바이원을 내기 쉬우니, 입력을 1-인덱스로 맞춰 넣는 편이 안전하다.
$n \le m$ 가정: 행이 열보다 많으면 행렬을 전치해 넣는다. 안 그러면 매칭이 깨진다.
오버플로: 비용이 크거나 $\infty$ 금지 간선을 쓰면 long long. 여러 $\infty$ 가 더해지지 않도록 $\infty$ 값을 (합해도 안전한) 적당히 큰 값으로.
최대화 부호: 반전 후 반환 비용도 다시 반전해 해석. 부호 실수는 "그럴듯한 오답"을 만든다.
여러 최적해: 최소 비용은 유일해도 배정(순열)은 여럿일 수 있다. 특정 tie-break가 필요하면 비용에 미세한 우선순위를 인코딩.
실수 비용: 부동소수 비교로 delta가 미세 오차를 내면 무한 루프 위험. 가능하면 정수화하거나 epsilon 비교.

헝가리안의 정당성은 전부 LP 쌍대성 + 상보적 여유에서 나온다. 잠재값 $$u,v$$ 가 "빡빡한 간선"을 만들어 가는 과정으로 이해하면 코드의 각 갱신이 왜 그런지 보인다.

Practice problem 최소 비용 작업 배정 선택 25m

R00641

최소 비용 작업 배정

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Level 9 · Master

Master

그래프 이론 · Master 단계

0/15 완료

Lesson 블로섬: 홀수 사이클을 접는다 필수 8m

일반 그래프의 최대 매칭

이분 그래프가 아닌 임의의 무방향 그래프에서 최대 매칭(서로 정점을 공유하지 않는 최대 간선 집합)을 찾는다. 이분 매칭의 쿤/홉크로프트–카프는 여기서 틀린다. 이유는 홀수 길이 사이클 때문이다.

왜 이분 알고리즘이 실패하나

이분 그래프엔 홀수 사이클이 없어 증가 경로를 단순 DFS로 찾을 수 있었다. 일반 그래프에서 홀수 사이클을 만나면, 사이클을 도는 방향에 따라 "매칭–비매칭 교대"가 깨져 진짜 증가 경로를 놓친다. 예: 삼각형에서 한 변을 매칭하면 남은 정점 하나를 순진한 DFS로는 절대 못 잇지만, 실제로는 사이클을 "접어" 처리하면 매칭을 키울 수 있는 경우가 생긴다.

블로섬(blossom)

에드몬즈의 통찰: 교대 탐색 중 발견되는 홀수 사이클(길이 $$2k+1$$ , 그중 $$k$$ 개가 매칭 간선)을 하나의 "수퍼 정점"으로 수축(contract) 한다. 이 수축된 홀수 사이클이 블로섬이다.

핵심 성질. 그래프 $$G$$ 에서 블로섬 $$B$$ 를 한 점으로 수축한 $$G/B$$ 가 증가 경로를 가지면, 그것을 블로섬 내부 경로로 펼쳐(expand) 원 그래프의 증가 경로로 복원할 수 있다. 반대도 성립.

따라서 "교대 BFS로 증가 경로를 찾되, 홀수 사이클을 만나면 수축하고 계속"이 알고리즘의 뼈대다.

베르주 정리와 튜트–베르주 공식

베르주 정리. 매칭 $$M$$ 이 최대 $\iff$ 증가 경로가 없다. (일반 그래프에서도 성립.)

최대 매칭의 크기는 다음으로 특징지어진다.

튜트–베르주 공식. 최대 매칭에서 매칭 안 되는 정점 수의 최소는
$\max_{U \subseteq V}\big(\,o(G - U) - |U|\,\big)$
여기서 $$o(G-U)$$ 는 $$U$$ 를 지운 그래프의 홀수 크기 컴포넌트 수. 따라서 최대 매칭 크기 $= \tfrac{1}{2}\big(|V| - \max_U (o(G-U)-|U|)\big)$ .

$U=\varnothing$ 에서 $$o(G)=0$$ 이면 완전 매칭 존재(튜트 정리의 특수형).

언제 쓰나

그래프가 이분이 아닐 때의 최대 매칭.
"서로 짝지을 수 있는 쌍"이 임의 관계(예: 상호 호환되는 원소 쌍)로 주어져 홀수 사이클이 생길 수 있는 문제.
최소 간선 덮개, 특정 커버링 문제의 하위 루틴.

복잡도

표준 블로섬(BFS 기반, LCA 수축): $$O(V^3)$$ . 정교판은 $$O(VE)$$ 또는 $O(E\sqrt V)$ (Micali–Vazirani, 구현 난도 매우 높음).
CP에서는 $$O(V^3)$$ 블로섬으로 $V \lesssim 500$ 정도까지 무난하다.

작은 예제

5-사이클 $1\!-\!2\!-\!3\!-\!4\!-\!5\!-\!1$ . 최대 매칭은 2(예: $\{1\!-\!2, 3\!-\!4\}$ , 정점 5는 남음). 순진한 이분식 DFS는 홀수 사이클에서 헤매지만, 블로섬은 5-사이클을 수축·펼침으로써 정확히 크기 2를 찾는다. 삼각형에 꼬리가 붙은 $1\!-\!2\!-\!3\!-\!1, 3\!-\!4$ 도 최대 매칭 2( $\{1\!-\!2, 3\!-\!4\}$ ).

Lesson 블로섬 알고리즘 구현 선택 8m

블로섬 구현 (C++)

BFS로 교대 트리를 키우며, 두 홀수-거리(라벨 짝) 정점이 만나면 그 LCA를 블로섬의 밑동(base)으로 삼아 수축한다. 정점은 1-인덱스.

match[v]: $$v$$ 의 짝(0이면 없음).
p[v]: 교대 트리에서의 부모.
base[v]: $$v$$ 가 속한 블로섬의 밑동(수축 대표).
BFS 큐에는 "바깥(even) 라벨" 정점만 넣는다.

#include <bits/stdc++.h>
using namespace std;

struct Blossom {
    int n;
    vector<vector<int>> g;
    vector<int> match, p, base;
    vector<bool> used, blossom;
    queue<int> q;
    Blossom(int n): n(n), g(n + 1), match(n + 1, 0), p(n + 1), base(n + 1) {}
    void addEdge(int u, int v) { g[u].push_back(v); g[v].push_back(u); }

    int lca(int a, int b) {
        vector<bool> vis(n + 1, false);
        while (true) { a = base[a]; vis[a] = true; if (!match[a]) break; a = p[match[a]]; }
        while (true) { b = base[b]; if (vis[b]) return b; b = p[match[b]]; }
    }
    void markPath(int v, int b, int child) {
        while (base[v] != b) {
            blossom[base[v]] = true;
            blossom[base[match[v]]] = true;
            p[v] = child; child = match[v]; v = p[match[v]];
        }
    }
    int findPath(int root) {
        fill(used.begin(), used.end(), false);
        fill(p.begin(), p.end(), 0);
        for (int i = 1; i <= n; i++) base[i] = i;
        used[root] = true;
        while (!q.empty()) q.pop();
        q.push(root);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (int to : g[v]) {
                if (base[v] == base[to] || match[v] == to) continue;
                if (to == root || (match[to] && p[match[to]])) {   // 블로섬 발견
                    int cur = lca(v, to);
                    fill(blossom.begin(), blossom.end(), false);
                    markPath(v, cur, to); markPath(to, cur, v);
                    for (int i = 1; i <= n; i++)
                        if (blossom[base[i]]) { base[i] = cur; if (!used[i]) { used[i] = true; q.push(i); } }
                } else if (!p[to]) {                                // 트리 확장
                    p[to] = v;
                    if (!match[to]) return to;                      // 증가 경로 끝점
                    else { used[match[to]] = true; q.push(match[to]); }
                }
            }
        }
        return 0;
    }
    int solve() {
        used.assign(n + 1, false); blossom.assign(n + 1, false);
        int res = 0;
        for (int v = 1; v <= n; v++) if (!match[v]) {
            int u = findPath(v);
            if (u) {                                               // 경로 따라 뒤집기
                res++;
                while (u) { int pv = p[u], ppv = match[pv]; match[u] = pv; match[pv] = u; u = ppv; }
            }
        }
        return res;
    }
};

이 구현은 5-사이클에서 2, 삼각형+꼬리에서 2를 반환한다(검증 완료).

Python (가독성 우선)

파이썬 블로섬은 느리므로 작은 $$n$$ 검증·학습용이다.

from collections import deque

class Blossom:
    def __init__(self, n):
        self.n = n
        self.g = [[] for _ in range(n + 1)]
        self.match = [0] * (n + 1)
    def add_edge(self, u, v):
        self.g[u].append(v); self.g[v].append(u)
    def _lca(self, a, b, base, p, match):
        vis = [False] * (self.n + 1)
        while True:
            a = base[a]; vis[a] = True
            if not match[a]: break
            a = p[match[a]]
        while True:
            b = base[b]
            if vis[b]: return b
            b = p[match[b]]
    def _mark(self, v, b, child, base, p, match, blossom):
        while base[v] != b:
            blossom[base[v]] = True; blossom[base[match[v]]] = True
            p[v] = child; child = match[v]; v = p[match[v]]
    def _find(self, root):
        n = self.n; match = self.match
        used = [False] * (n + 1); p = [0] * (n + 1); base = list(range(n + 1))
        used[root] = True; q = deque([root])
        while q:
            v = q.popleft()
            for to in self.g[v]:
                if base[v] == base[to] or match[v] == to: continue
                if to == root or (match[to] and p[match[to]]):
                    cur = self._lca(v, to, base, p, match)
                    blossom = [False] * (n + 1)
                    self._mark(v, cur, to, base, p, match, blossom)
                    self._mark(to, cur, v, base, p, match, blossom)
                    for i in range(1, n + 1):
                        if blossom[base[i]]:
                            base[i] = cur
                            if not used[i]: used[i] = True; q.append(i)
                elif not p[to]:
                    p[to] = v
                    if not match[to]:
                        return to, p
                    used[match[to]] = True; q.append(match[to])
        return 0, p
    def solve(self):
        res = 0
        for v in range(1, self.n + 1):
            if not self.match[v]:
                u, p = self._find(v)
                if u:
                    res += 1
                    while u:
                        pv = p[u]; ppv = self.match[pv]
                        self.match[u] = pv; self.match[pv] = u; u = ppv
        return res

동작 요약

미매칭 정점 root마다 교대 BFS.
even 정점 $$v$$ 에서 이웃 $$to$$ 를 보며:
- $$to$$ 가 even(또는 root)이면 홀수 사이클 → LCA로 수축.
- $$to$$ 가 미탐색이면 트리 확장; $$to$$ 가 미매칭이면 증가 경로 발견.
발견 시 p 포인터를 따라 매칭을 뒤집어 크기 $$+1$$ .

Lesson 심화: 최소 간선 덮개·완전 매칭·함정 선택 8m

응용과 모델링

이분이 아닌 짝짓기

"임의의 두 원소가 호환되면 짝지을 수 있다"류(호환 관계가 삼각형·홀수 사이클을 만들 수 있음)는 반드시 일반 매칭. 그래프가 이분인지부터 판별(2-색칠 가능?)하고, 아니면 블로섬.

최소 간선 덮개

연결 그래프(고립점 없음)에서 최소 간선 덮개 $= |V| - (\text{최대 매칭})$ . 일반 그래프에서도 갈라이(Gallai) 항등식으로 성립하므로 블로섬으로 최대 매칭을 구해 답한다.

최대 독립 집합과의 관계

일반 그래프의 최대 독립 집합은 NP-난해라 매칭으로 직접 안 풀린다(이분 그래프에서만 쾨니그로 가능). 일반 매칭이 다항 시간인 것과 독립 집합이 어려운 것을 혼동하지 말 것.

완전 매칭 판정

$$|V|$$ 가 짝수이고 최대 매칭 $$= |V|/2$$ 이면 완전 매칭 존재. 튜트 정리로도 판정 가능하지만, 실전에선 블로섬을 돌려 크기를 보는 것이 간단.

엣지 케이스와 흔한 버그

LCA 계산: 블로섬의 밑동을 찾는 lca가 정확해야 한다. base[]를 따라 올라가며 방문 표시하는 로직에서 match 없는 정점(트리 루트) 처리를 빠뜨리면 무한 루프.
수축 후 큐 삽입: 블로섬에 새로 편입된 정점 중 아직 used가 아닌 것을 큐에 넣어야 탐색이 이어진다. 이를 빼면 증가 경로를 놓친다.
base vs 실제 정점: 이웃 비교 시 base[v] == base[to](같은 블로섬이면 무시)와 match[v] == to(이미 매칭 간선)를 모두 걸러야 한다. 하나라도 빠지면 잘못된 사이클을 잡는다.
부모 포인터 방향: markPath에서 p를 뒤집어 세팅하는 순서가 미묘하다. 증가 경로 복원(while(u) 루프)과 일관되게 맞춰야 한다.
1-인덱스: match[v]==0을 "미매칭"으로 쓰므로 정점 번호는 1부터. 0-인덱스로 바꾸면 이 관례가 깨진다.
자기 루프·다중 간선: 자기 루프는 매칭에 무의미하므로 제거. 다중 간선은 무해하나 상수만 늘린다.
검증: 작은 $$n$$ 에서 완전탐색(모든 매칭 나열)과 대조하면 수축/펼침 버그를 잡기 좋다. 5-사이클, 페테르센 그래프 등 홀수 사이클이 있는 케이스를 꼭 넣어 본다.

일반 매칭(블로섬)은 구현이 까다롭기로 유명하다. 위 $$O(V^3)$$ 버전을 검증된 그대로 쓰고, 가중치가 붙으면 별도의 가중 일반 매칭(가중 블로섬) 강의로 넘어간다.

Practice problem 결투의 짝짓기 선택 25m

R00695

결투의 짝짓기

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

다이아몬드 II 지금 풀기

Lesson 지배 관계와 준지배자 정리 필수 8m

지배 관계

방향 그래프와 시작 정점 $$r$$ 이 있다. 정점 $$u$$ 가 정점 $$w$$ 를 지배(dominate) 한다는 것은, $$r$$ 에서 $$w$$ 로 가는 모든 경로가 반드시 $$u$$ 를 지난다는 뜻이다. 자기 자신도 자신을 지배한다.

$$w$$ 를 지배하는 정점들 중 $$w$$ 자신을 제외하고 가장 가까운(다른 모든 지배자에게 지배당하는) 것을 직접 지배자(immediate dominator) $\mathrm{idom}(w)$ 라 한다.

정리. $$r$$ 에서 도달 가능한 각 정점 $w \ne r$ 은 유일한 $\mathrm{idom}(w)$ 를 가지며, 간선 $\mathrm{idom}(w)\to w$ 들을 모으면 트리(도미네이터 트리)가 된다. 이 트리에서 $$u$$ 가 $$w$$ 의 조상 $\iff$ $$u$$ 가 $$w$$ 를 지배.

컴파일러 최적화(제어 흐름), "이 노드가 막히면 도달 불가능해지는 정점", 네트워크 필수 경유지 분석 등에 쓴다.

준지배자(semidominator)

Lengauer–Tarjan의 핵심 보조 개념이다. 먼저 $$r$$ 에서 DFS 트리를 만들고 각 정점에 방문 순서(dfs 번호)를 준다. 정점 $$w$$ 의 준지배자 $\mathrm{sdom}(w)$ 는:

$$$ \mathrm{sdom}(w) = \min\{\, \mathrm{dfsnum}(v) : \text{경로 } v = v_0, v_1, \dots, v_k = w,\ \mathrm{dfsnum}(v_i) > \mathrm{dfsnum}(w)\ (0$

즉 "중간 정점들이 모두 $$w$$ 보다 dfs 번호가 큰" 경로로 $$w$$ 에 닿을 수 있는 가장 작은 번호의 정점. 직관적으로 $\mathrm{idom}$ 의 후보/근사다.

준지배자 정리(요지). $$w$$ 의 준지배자는 위 특수 경로들만 보면 계산할 수 있고, $\mathrm{idom}(w)$ 는 $\mathrm{sdom}$ 들로부터 결정된다: DFS 트리에서 $\mathrm{sdom}(w)$ 와 $$w$$ 사이 경로상 $\mathrm{sdom}$ 이 최소인 정점 $$u$$ 에 대해, $\mathrm{sdom}(u)=\mathrm{sdom}(w)$ 이면 $\mathrm{idom}(w)=\mathrm{sdom}(w)$ , 아니면 $\mathrm{idom}(w)=\mathrm{idom}(u)$ .

이 정리 덕분에 지배 관계를 정점마다 직접 검사하지 않고 dfs 역순 한 번에 계산한다.

복잡도

Lengauer–Tarjan: 경로 압축 DSU를 쓰면 $O(E\log V)$ (단순판) 또는 $O(E\,\alpha(V))$ (정교판). 실전 구현은 대개 $O(E\log V)$ 이며 매우 빠르다.
순진하게 "각 정점을 지워 도달성 재검사"하면 $O(V\cdot E)$ — 작은 그래프 검증용.

작은 예제

간선 $0\!\to\!1,\ 0\!\to\!2,\ 1\!\to\!3,\ 2\!\to\!3,\ 3\!\to\!4$ , 루트 $$0$$ .

$$1, 2$$ 는 각각 $$0$$ 에서만 오므로 $\mathrm{idom}=0$ .
$$3$$ 은 $$1$$ 과 $$2$$ 두 경로로 도달 → 공통 지배자는 $$0$$ 뿐 → $\mathrm{idom}(3)=0$ .
$$4$$ 는 오직 $$3$$ 을 통해서만 → $\mathrm{idom}(4)=3$ .

도미네이터 트리: $$0$$ 의 자식이 $$1,2,3$$ , $$3$$ 의 자식이 $$4$$ .

Lesson Lengauer–Tarjan 구현 선택 8m

Lengauer–Tarjan 구현 (C++)

DFS로 번호를 매기고(정점 $\to$ dfs번호 ord, 역 rev), dfs 역순으로 준지배자를 계산한 뒤 버킷과 DSU(eval/link)로 idom을 확정한다. DSU의 find는 경로상 sdom이 최소인 대표를 반환하도록 라벨을 갱신한다.

#include <bits/stdc++.h>
using namespace std;

struct Dominators {
    int n, timer = 0;
    vector<vector<int>> g, rg, bucket;
    vector<int> par, ord, rev, sdom, idom, dsu, label;
    Dominators(int n): n(n), g(n), rg(n), bucket(n), par(n, -1), ord(n, -1),
        rev(n, -1), sdom(n, -1), idom(n, -1), dsu(n), label(n) {
        for (int i = 0; i < n; i++) { dsu[i] = i; label[i] = i; }
    }
    void addEdge(int u, int v) { g[u].push_back(v); rg[v].push_back(u); }

    void dfs(int u) {
        ord[u] = timer; rev[timer] = u; sdom[u] = timer; timer++;
        for (int v : g[u]) if (ord[v] < 0) { par[v] = u; dfs(v); }
    }
    // 경로 압축하며 sdom-label 최소 대표 반환
    int find(int u, int x = 0) {
        if (dsu[u] == u) return x ? -1 : u;
        int v = find(dsu[u], x + 1);
        if (v < 0) return u;
        if (sdom[label[dsu[u]]] < sdom[label[u]]) label[u] = label[dsu[u]];
        dsu[u] = v;
        return x ? v : label[u];
    }
    vector<int> run(int r) {                 // 반환: idom[정점] (도달 불가면 -1)
        dfs(r);
        for (int i = timer - 1; i >= 1; i--) {
            int w = rev[i];
            for (int v : rg[w]) if (ord[v] >= 0) {
                int u = find(v);
                if (sdom[u] < sdom[w]) sdom[w] = sdom[u];
            }
            bucket[rev[sdom[w]]].push_back(w);
            dsu[w] = par[w];
            for (int v : bucket[par[w]]) {
                int u = find(v);
                idom[v] = (sdom[u] < sdom[v]) ? u : par[w];
            }
            bucket[par[w]].clear();
        }
        for (int i = 1; i < timer; i++) {
            int w = rev[i];
            if (idom[w] != rev[sdom[w]]) idom[w] = idom[idom[w]];  // 최종 확정
        }
        idom[r] = r;
        vector<int> res(n, -1);
        for (int i = 0; i < timer; i++) { int w = rev[i]; res[w] = idom[w]; }
        return res;
    }
};

위 예제에서 run(0)은 $\mathrm{idom}[1]=\mathrm{idom}[2]=\mathrm{idom}[3]=0,\ \mathrm{idom}[4]=3$ 을 반환한다(루트는 자기 자신).

단계별 요약

DFS로 dfs 번호, 부모 par, 역매핑 rev 준비.
dfs 번호 역순으로 각 $$w$$ :
- 역간선(전임자)들의 find로 $\mathrm{sdom}(w)$ 갱신.
- $$w$$ 를 $\mathrm{sdom}(w)$ 의 버킷에 넣음.
- dsu[w] = par[w]로 트리에 링크.
- $\mathrm{par}(w)$ 버킷을 처리해 잠정 idom 확정.
전방 패스로 idom[w] != rev[sdom[w]]인 경우 idom[w] = idom[idom[w]]로 보정.

실무 팁

정점 번호가 크거나 도달 불가 정점이 섞이면 ord[v] >= 0 검사로 걸러야 한다(위 코드에 반영).
도미네이터 트리 위에서 서브트리 크기, 조상 질의(LCA) 등을 얹어 "노드 $$x$$ 가 막히면 도달 불가능해지는 정점 수 = 도미네이터 트리에서 $$x$$ 의 서브트리 크기 $$-1$$ " 같은 질의를 처리한다.

Lesson 심화: 필수 경유·취약 정점·함정 선택 8m

응용

필수 경유 정점(must-pass)

" $$r$$ 에서 $$t$$ 로 가는 모든 경로가 반드시 지나는 정점" = 도미네이터 트리에서 $$t$$ 의 조상들( $r \dots \mathrm{idom}(t) \dots t$ 경로). 하나의 트리 경로로 즉시 답한다.

취약 정점 / 서브트리 크기

정점 $$x$$ 를 제거하면 도달 불가능해지는 정점 = 도미네이터 트리에서 $$x$$ 의 진서브트리. 서브트리 크기 계산으로 "가장 많은 정점을 끊는 단일 지점"을 찾는다.

컴파일러/제어 흐름

지배 트리는 SSA 변환, 루프 판별(자연 루프의 헤더는 백엣지 대상이 백엣지 출발을 지배), 코드 이동 등의 기반이다.

사후 지배자(post-dominator)

간선을 모두 뒤집고 싱크를 루트로 삼아 같은 알고리즘을 돌리면 post-dominator tree를 얻는다("이후 반드시 지나는 정점").

무방향/역방향 주의

지배 관계는 방향 그래프 + 시작점 개념이다. 시작점이 바뀌면 도미네이터 트리도 완전히 달라진다. 무방향 그래프의 "필수 통과 정점"은 도미네이터가 아니라 단절점/블록-컷 트리로 다뤄야 한다(BCC 강의 참고).

엣지 케이스와 흔한 버그

도달 불가 정점: $$r$$ 에서 못 가는 정점은 idom이 없다(-1). 역간선 순회에서 ord[v] >= 0으로 반드시 걸러야 하며, 안 그러면 sdom이 오염된다.
DSU find의 이중 반환: 위 구현의 find는 인자 x로 "재귀 최상위 여부"를 구분해 라벨 압축과 대표 반환을 함께 한다. 이 미묘한 재귀를 함부로 바꾸면 라벨 갱신이 깨진다.
전방 보정 패스 누락: idom[w] = idom[idom[w]] 보정을 빼먹으면 $\mathrm{sdom}\ne\mathrm{idom}$ 인 정점의 idom이 틀린 채 남는다. 반드시 dfs 번호 오름차순으로 수행(부모의 idom이 먼저 확정되어야 함).
자기 루프·다중 간선: 지배 관계에 무해하지만 역간선 리스트에 중복이 쌓이면 상수만 커진다. 필요시 정리.
재귀 깊이: DFS가 깊으면( $V\sim 10^5$ 사슬) 스택 오버플로. 반복형 DFS로 바꾸거나 스택 한도를 늘린다.
루트 처리: idom[r] = r로 명시. 루트를 일반 정점처럼 두면 트리 구성 시 자기참조 루프가 꼬인다.
검증: 작은 그래프에서는 "정점 $$x$$ 를 지운 뒤 $$w$$ 가 여전히 도달 가능한가"를 완전탐색으로 돌려 도미네이터 트리(조상 관계)와 대조하면 구현 오류를 잡기 쉽다.

Lengauer–Tarjan은 CP에서 자주 나오진 않지만, 나오면 이 구현을 그대로 쓰는 것이 안전하다. 준지배자 정리를 이해하면 각 패스가 무엇을 확정하는지 보인다.

Practice problem 관문 도시 선택 25m

R00622

관문 도시

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

레이팅 미적용 지금 풀기

Lesson 모든 쌍 최소 컷과 등가 유량 트리 필수 8m

모든 쌍 최소 컷

무방향 가중 그래프에서 임의의 두 정점 $$s,t$$ 사이 최소 컷(= 최대 유량, 최대유량-최소컷 정리)을 알고 싶다. 쌍이 $\binom{n}{2}$ 개이니 매번 최대 유량을 돌리면 $$O(n^2)$$ 번의 유량 계산이 필요하다.

고모리–후 정리. $$n$$ 개 정점의 무방향 그래프에는, 단 $$n-1$$ 개의 간선을 가진 가중 트리 $$T$$ (고모리–후 트리)가 존재하여, 임의의 $$s,t$$ 에 대해 원 그래프의 최소 $$s$$ - $$t$$ 컷 값 $$=$$ $$T$$ 에서 $$s$$ – $$t$$ 경로상 가장 작은 간선 가중치와 같다.

즉 $\binom{n}{2}$ 개의 최소 컷 값이 트리 하나에 전부 압축된다. 게다가 그 최소 간선을 트리에서 제거하면 생기는 두 컴포넌트가 실제 최소 컷의 정점 분할을 준다.

왜 트리 하나로 충분한가 (등가 유량 트리)

핵심은 누적 성질: 세 정점 $$a,b,c$$ 에 대해

$\mathrm{mincut}(a,c) \ge \min\big(\mathrm{mincut}(a,b),\ \mathrm{mincut}(b,c)\big).$

이 "울트라메트릭 유사" 부등식 때문에, 임의의 쌍의 최소 컷은 사실 서로 다른 값이 최대 $$n-1$$ 개뿐이고 트리 경로의 최소 간선으로 표현된다. 고모리–후 트리는 이 구조를 명시적으로 만든 것으로, 등가 유량 트리(equivalent flow tree) 라고도 한다.

언제 쓰나

모든 쌍 최소 컷/최대 유량이 필요할 때(질의가 많은 경우 전처리).
"그래프를 $$k$$ 조각으로 나누는 최소 비용", 최소 컷 기반 클러스터링.
특정 쌍이 아니라 "가장 약한 연결(전역 최소 컷)"이나 여러 쌍을 한꺼번에 물을 때.

복잡도

거스필드(Gusfield) 알고리즘: 최대 유량을 정확히 $$n-1$$ 번 호출한다. 각 유량이 $O(\text{maxflow})$ 이므로 전체 $O(n \cdot \text{maxflow})$ . 원 고모리–후 알고리즘의 정점 축약 없이도 등가 트리를 얻는 간결판이다.

작은 예제

4-사이클 $0\!-\!1\!-\!2\!-\!3\!-\!0$ 의 각 간선 용량 3, 그리고 대각 $0\!-\!2$ 용량 1.

$\mathrm{mincut}(0,1)$ : $$0$$ 을 나머지와 분리하려면 $0\!-\!1(3)+0\!-\!3(3)$ 중 더 작은 컷을 찾는데, $$0$$ 주변 간선 합이 $$3+3+1=7$$ 이나 실제 최소는 이웃을 적절히 묶어 6.
모든 쌍을 계산해 보면 값들은 $$6$$ 또는 $$7$$ 뿐이고, 이 관계가 트리 하나(간선 3개)로 정확히 재현된다.

(강의 구현 절의 검증 코드는 이 그래프에서 고모리–후 트리 질의와 직접 최대 유량이 모든 6쌍에서 일치함을 확인한다.)

Lesson 거스필드 알고리즘 구현 선택 8m

거스필드 알고리즘 (C++)

아이디어: 부모 배열 par를 모두 0으로 시작. $$i=1..n-1$$ 각각에 대해 원 그래프에서 $\mathrm{mincut}(i, \mathrm{par}[i])$ 를 구해 트리 간선 가중치로 삼고, $$i$$ 쪽 최소 컷 집합(잔여 그래프에서 $$i$$ 로부터 도달 가능한 정점들)에 있는 다른 정점들의 부모를 $$i$$ 로 갱신한다.

무방향 간선은 최대 유량 그래프에서 양방향 용량 $$c$$ 로 넣는다. 매 쌍마다 그래프를 새로 빌드(잔여 상태를 초기화)하는 것이 안전하다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

struct Dinic {
    struct E { int to; ll cap; int rev; };
    vector<vector<E>> g; vector<int> level, it; int n;
    Dinic(int n): g(n), level(n), it(n), n(n) {}
    void add(int u, int v, ll c) {              // 무방향: 양쪽 용량 c
        g[u].push_back({v, c, (int)g[v].size()});
        g[v].push_back({u, c, (int)g[u].size() - 1});
    }
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1); queue<int> q; level[s] = 0; q.push(s);
        while (!q.empty()) { int u = q.front(); q.pop();
            for (auto& e : g[u]) if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[u] + 1; q.push(e.to); } }
        return level[t] >= 0;
    }
    ll dfs(int u, int t, ll f) { if (u == t) return f;
        for (int& i = it[u]; i < (int)g[u].size(); i++) { E& e = g[u][i];
            if (e.cap > 0 && level[u] + 1 == level[e.to]) { ll d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) { e.cap -= d; g[e.to][e.rev].cap += d; return d; } } }
        return 0;
    }
    ll maxflow(int s, int t) { ll fl = 0;
        while (bfs(s, t)) { fill(it.begin(), it.end(), 0); while (ll f = dfs(s, t, INF)) fl += f; }
        return fl;
    }
};

int n;
vector<array<ll,3>> edges;                        // {u, v, cap}
Dinic build() { Dinic d(n); for (auto& e : edges) d.add((int)e[0], (int)e[1], e[2]); return d; }

// 고모리-후 트리: par[i], weight[i] = mincut(i, par[i])
void gomory_hu(vector<int>& par, vector<ll>& weight) {
    par.assign(n, 0); weight.assign(n, 0);
    for (int i = 1; i < n; i++) {
        Dinic d = build();
        weight[i] = d.maxflow(i, par[i]);
        // i 쪽 최소 컷 집합 = 잔여 그래프에서 i로부터 도달 가능
        vector<bool> vis(n, false); queue<int> q; q.push(i); vis[i] = true;
        while (!q.empty()) { int u = q.front(); q.pop();
            for (auto& e : d.g[u]) if (e.cap > 0 && !vis[e.to]) { vis[e.to] = true; q.push(e.to); } }
        for (int j = i + 1; j < n; j++)
            if (vis[j] && par[j] == par[i]) par[j] = i;   // 같은 쪽에 있으면 부모 재배치
    }
}

질의: 두 정점의 최소 컷

트리를 만들었으면 $\mathrm{mincut}(a,b)$ 는 트리 $$a$$ – $$b$$ 경로의 최소 간선 가중치다. 작은 $$n$$ 이면 매 질의를 BFS로, 질의가 많으면 트리에서 최소 간선 LCA(sparse table)로 $O(\log n)$ 에 답한다.

ll query(vector<int>& par, vector<ll>& weight, int a, int b) {
    // 트리 인접 리스트 구성
    vector<vector<pair<int,ll>>> t(n);
    for (int i = 1; i < n; i++) { t[i].push_back({par[i], weight[i]}); t[par[i]].push_back({i, weight[i]}); }
    vector<ll> best(n, INF); vector<bool> vis(n, false);
    queue<int> q; q.push(a); vis[a] = true; best[a] = INF;
    while (!q.empty()) { int u = q.front(); q.pop();
        for (auto [v, w] : t[u]) if (!vis[v]) { vis[v] = true; best[v] = min(best[u], w); q.push(v); } }
    return best[b];
}

이 구현은 검증에서 모든 정점 쌍에 대해 트리 질의값 = 직접 최대 유량값임을 확인했다(4-정점 예제 6쌍 전부 일치).

Python 개요

파이썬도 동일 구조다. Dinic을 클래스로 두고, gomory_hu에서 매 $$i$$ 마다 그래프를 새로 만들어 maxflow(i, par[i])를 부르고 잔여 BFS로 도달 집합을 구해 par를 갱신한다. $$n$$ 이 수십~수백이면 충분히 돌아간다.

Lesson 심화: 거스필드 vs 원본·무방향 전용·함정 선택 8m

거스필드 vs 원 고모리–후

원 알고리즘(1961): 최소 컷마다 한쪽 집합을 정점 축약(contraction) 하며 진행한다. 정확하지만 축약 그래프 관리가 번거롭다.
거스필드(1990): 축약 없이 항상 원 그래프에서 $$n-1$$ 번 최대 유량만 돌린다. 구현이 훨씬 간단하고, 만들어진 트리는 "가중치 트리로서 등가"다. 단, 거스필드 트리는 원 알고리즘 트리와 간선/모양이 다를 수 있다 — 그러나 모든 쌍의 최소 컷 값은 동일하게 재현한다(등가 유량 트리이므로). CP에서는 값만 맞으면 되므로 거스필드로 충분하다.

주의: 거스필드 트리의 개별 간선을 "실제 최소 컷의 물리적 위치"로 해석하려면 조심해야 한다. 최소 컷 값은 정확하지만, 특정 간선이 원 그래프의 어떤 컷에 대응하는지는 원 알고리즘 쪽이 더 직접적이다.

무방향 전용

고모리–후 트리는 무방향 그래프의 성질이다. 방향 그래프에서는 $\mathrm{mincut}(s,t)$ 와 $\mathrm{mincut}(t,s)$ 가 다를 수 있어 등가 유량 트리가 일반적으로 존재하지 않는다. 방향 그래프의 모든 쌍 최소 컷은 별도 기법이 필요하며 단일 트리로 압축되지 않는다.

응용

전역 최소 컷(global min cut): 고모리–후 트리의 가장 가벼운 간선이 전역 최소 컷 값이다(Stoer–Wagner의 대안).
다중 소스/싱크 질의: 여러 쌍의 컷을 물으면 트리 전처리 후 각 질의 $O(\log n)$ .
네트워크 신뢰도/클러스터링: 임계 컷 기준으로 트리 간선을 잘라 계층적 분할.

엣지 케이스와 흔한 버그

무방향 간선 용량: 최대 유량 그래프에서 무방향 간선은 양쪽 모두 용량 $$c$$ . 한쪽만 넣거나 역간선을 0으로 두면 방향 그래프가 되어 값이 틀린다.
매 쌍 그래프 재빌드: maxflow 후 잔여 용량이 소모된 그래프를 다음 쌍에 재사용하면 안 된다. 매 $$i$$ 마다 새로 build(위 코드처럼)하거나 용량을 원복해야 한다.
부모 재배치 조건: par[j] == par[i] 이고 잔여 도달 집합에 $$j$$ 가 있을 때만 par[j] = i. 이 조건을 빼면 트리가 틀어진다.
도달 집합 방향: 최소 컷 집합은 $$i$$ 로부터 잔여 그래프에서 도달 가능한 정점들. 원 그래프 도달성으로 착각하면 안 된다.
다중 간선: 같은 두 정점 사이 평행 간선은 용량을 합산해 넣거나 그대로 여러 개 추가(유량엔 동일). 무해하다.
연결성: 그래프가 비연결이면 서로 다른 컴포넌트 간 최소 컷은 0. 필요시 컴포넌트별로 처리하거나 0 간선으로 이어 준다.
오버플로: 용량 합이 크면 long long.

고모리–후 트리는 결국 "무방향 그래프의 모든 쌍 최소 컷 = 트리 경로 최소 간선"이라는 한 문장으로 요약된다. 최대 유량(디닉)이 탄탄하면 거스필드는 그 위에 얇게 얹히는 층이다.

Lesson 가중 블로섬: LP 쌍대와 원시–쌍대 필수 8m

가중 일반 매칭

임의의 무방향 그래프의 간선에 가중치 $$w(e)$$ 가 붙어 있을 때, 매칭 $$M$$ 의 가중치 합 $\sum_{e\in M} w(e)$ 을 최대화하는 것이 최대 가중 일반 매칭(maximum weight general matching) 이다. 이분 그래프의 가중 매칭(=할당/헝가리안)과 달리 홀수 사이클(블로섬) 까지 다뤄야 하므로 가장 복잡한 매칭 문제다.

변형: 최대 가중 완전 매칭(모든 정점이 매칭되면서 가중치 최대), 최소 가중 완전 매칭, 정해진 크기의 매칭 등.

LP와 홀수 집합 제약

가중 매칭의 정수 최적성은 다음 LP(에드몬즈)로 특징지어진다. 변수 $x_e \in [0,1]$ :

$\max \sum_e w(e)\,x_e \quad\text{s.t.}\quad \sum_{e \ni v} x_e \le 1\ (\forall v),\quad \sum_{e \subseteq U} x_e \le \tfrac{|U|-1}{2}\ (\forall \text{홀수 } U).$

마지막 홀수 집합 제약(blossom inequality) 이 이분 그래프엔 없던 핵심이다. 홀수 크기 정점 집합 $$U$$ 안의 간선은 최대 $\lfloor |U|/2\rfloor$ 개만 매칭될 수 있음을 강제한다.

쌍대 변수와 상보적 여유

쌍대는 각 정점 $$v$$ 에 $$y_v$$ , 각 홀수 집합 $$B$$ 에 $z_B \ge 0$ 을 둔다. 간선 $$e=(u,v)$$ 의 여유(slack):

$\mathrm{slack}(e) = y_u + y_v + \sum_{B \supseteq e} z_B - w(e) \ \ge 0.$

상보적 여유. 최적 매칭의 간선은 여유가 0(빡빡한 간선)이고, $$z_B > 0$$ 인 블로섬 $$B$$ 는 "거의 꽉 찬"(짝지어진) 상태다.

가중 블로섬 알고리즘은 이 쌍대 변수 $$y, z$$ 를 유지하며 원시–쌍대(primal–dual) 로 진행한다: 빡빡한 간선으로 교대 트리를 키우다 막히면, 쌍대 변수를 $\delta$ 만큼 조정해 새 빡빡한 간선을 만들고(또는 블로섬을 수축/팽창), 증가 경로가 생기면 매칭을 키운다. 헝가리안의 잠재값 조정을 블로섬 수축까지 포함하도록 일반화한 것이다.

언제 쓰나 / 복잡도

그래프가 이분이 아니며 간선 가중치 최적 매칭이 필요할 때.
최대/최소 가중 완전 매칭(예: 정점을 쌍으로 최적 배치).
표준 $$O(n^3)$$ 구현으로 $n \lesssim 400{-}500$ 까지 실전 가능.

작은 예제

정점 4개 완전 그래프, 가중치 $$w(1,2)=w(3,4)=10$$ , $$w(1,3)=w(2,4)=1$$ , $$w(1,4)=w(2,3)=1$$ .

완전 매칭 후보: $\{1\!-\!2,3\!-\!4\}=20$ , $\{1\!-\!3,2\!-\!4\}=2$ , $\{1\!-\!4,2\!-\!3\}=2$ .
최대 가중 매칭 $$= 20$$ ( $\{1\!-\!2, 3\!-\!4\}$ ).

일반적으로 홀수 사이클(예: 삼각형 + 매다는 간선)이 섞이면 단순 그리디가 틀리며, 쌍대 변수와 블로섬 수축이 최적을 보장한다. 아래 구현은 무작위 소규모 그래프 300개에서 완전탐색과 모두 일치함을 확인했다.

Lesson 가중 블로섬 $O(n^3)$ 구현 선택 8m

가중 블로섬 $$O(n^3)$$ 구현 (C++)

아래는 널리 검증된 표준 참조 구현(UOJ #79 계열)이다. 매우 미묘하므로 그대로 사용하기를 권한다. 정점은 1-인덱스, g[u][v].w에 가중치(간선 없으면 0). 반환은 최대 가중치 합.

핵심 배열:
- lab[v]: 쌍대 변수 $$y_v$$ (블로섬은 $$z$$ 를 lab에 반영).
- match_[v]: 짝. st[v]: $$v$$ 가 속한 (수축된) 블로섬 대표.
- S[b]: 교대 트리 라벨(0=even/outer, 1=inner, -1=미방문).
- slack[x], flower[b](블로섬 구성), flower_from, pa(부모).

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9, MAXN = 505;
struct E { int u, v, w; };
int n, n_x;
E g[MAXN][MAXN];
int lab[MAXN], match_[MAXN], slack[MAXN], st[MAXN], pa[MAXN];
int flower_from[MAXN][MAXN], S[MAXN], vis[MAXN];
vector<int> flower[MAXN];
deque<int> q;

int e_delta(const E& e) { return lab[e.u] + lab[e.v] - g[e.u][e.v].w * 2; }
void update_slack(int u, int x) { if (!slack[x] || e_delta(g[u][x]) < e_delta(g[slack[x]][x])) slack[x] = u; }
void set_slack(int x) { slack[x] = 0; for (int u = 1; u <= n; u++) if (g[u][x].w > 0 && st[u] != x && S[st[u]] == 0) update_slack(u, x); }
void q_push(int x) { if (x <= n) q.push_back(x); else for (int f : flower[x]) q_push(f); }
void set_st(int x, int b) { st[x] = b; if (x > n) for (int f : flower[x]) set_st(f, b); }
int get_pr(int b, int xr) {
    int pr = find(flower[b].begin(), flower[b].end(), xr) - flower[b].begin();
    if (pr % 2 == 1) { reverse(flower[b].begin() + 1, flower[b].end()); return (int)flower[b].size() - pr; }
    return pr;
}
void set_match(int u, int v) {
    match_[u] = g[u][v].v;
    if (u > n) { E e = g[u][v]; int xr = flower_from[u][e.u], pr = get_pr(u, xr);
        for (int i = 0; i < pr; i++) set_match(flower[u][i], flower[u][i ^ 1]);
        set_match(xr, v); rotate(flower[u].begin(), flower[u].begin() + pr, flower[u].end()); }
}
void augment(int u, int v) { while (true) { int xnv = st[match_[u]]; set_match(u, v); if (!xnv) return;
    set_match(xnv, st[pa[xnv]]); u = st[pa[xnv]]; v = xnv; } }
int get_lca(int u, int v) { static int t = 0; for (++t; u || v; swap(u, v)) { if (u == 0) continue;
    if (vis[u] == t) return u; vis[u] = t; u = st[match_[u]]; if (u) u = st[pa[u]]; } return 0; }
void add_blossom(int u, int lca, int v) {
    int b = n + 1; while (b <= n_x && st[b]) ++b; if (b > n_x) ++n_x;
    lab[b] = 0; S[b] = 0; match_[b] = match_[lca]; flower[b].clear(); flower[b].push_back(lca);
    for (int x = u, y; x != lca; x = st[pa[y]]) { flower[b].push_back(x); flower[b].push_back(y = st[match_[x]]); q_push(y); }
    reverse(flower[b].begin() + 1, flower[b].end());
    for (int x = v, y; x != lca; x = st[pa[y]]) { flower[b].push_back(x); flower[b].push_back(y = st[match_[x]]); q_push(y); }
    set_st(b, b);
    for (int x = 1; x <= n_x; x++) g[b][x].w = g[x][b].w = 0;
    for (int x = 1; x <= n; x++) flower_from[b][x] = 0;
    for (int f : flower[b]) {
        for (int x = 1; x <= n_x; x++)
            if (g[b][x].w == 0 || e_delta(g[f][x]) < e_delta(g[b][x])) g[b][x] = g[f][x], g[x][b] = g[x][f];
        for (int x = 1; x <= n; x++) if (flower_from[f][x]) flower_from[b][x] = f;
    }
    set_slack(b);
}
void expand_blossom(int b) {
    for (int f : flower[b]) set_st(f, f);
    int xr = flower_from[b][g[b][pa[b]].u], pr = get_pr(b, xr);
    for (int i = 0; i < pr; i += 2) { int xs = flower[b][i], xns = flower[b][i + 1];
        pa[xs] = g[xns][xs].u; S[xs] = 1; S[xns] = 0; slack[xs] = 0; set_slack(xns); q_push(xns); }
    S[xr] = 1; pa[xr] = pa[b];
    for (int i = pr + 1; i < (int)flower[b].size(); i++) { int xs = flower[b][i]; S[xs] = -1; set_slack(xs); }
    st[b] = 0;
}
bool on_found_edge(const E& e) {
    int u = st[e.u], v = st[e.v];
    if (S[v] == -1) { pa[v] = e.u; S[v] = 1; int nu = st[match_[v]]; slack[v] = slack[nu] = 0; S[nu] = 0; q_push(nu); }
    else if (S[v] == 0) { int lca = get_lca(u, v);
        if (!lca) { augment(u, v); augment(v, u); return true; } else add_blossom(u, lca, v); }
    return false;
}
bool matching() {
    fill(S + 1, S + n_x + 1, -1); fill(slack + 1, slack + n_x + 1, 0); q.clear();
    for (int x = 1; x <= n_x; x++) if (st[x] == x && !match_[x]) { pa[x] = 0; S[x] = 0; q_push(x); }
    if (q.empty()) return false;
    while (true) {
        while (!q.empty()) { int u = q.front(); q.pop_front(); if (S[st[u]] == 1) continue;
            for (int v = 1; v <= n; v++) if (g[u][v].w > 0 && st[u] != st[v]) {
                if (e_delta(g[u][v]) == 0) { if (on_found_edge(g[u][v])) return true; }
                else update_slack(u, st[v]); } }
        int d = INF;
        for (int b = n + 1; b <= n_x; b++) if (st[b] == b && S[b] == 1) d = min(d, lab[b] / 2);
        for (int x = 1; x <= n_x; x++) if (st[x] == x && slack[x]) {
            if (S[x] == -1) d = min(d, e_delta(g[slack[x]][x]));
            else if (S[x] == 0) d = min(d, e_delta(g[slack[x]][x]) / 2); }
        for (int u = 1; u <= n; u++) { if (S[st[u]] == 0) { if (lab[u] <= d) return false; lab[u] -= d; }
            else if (S[st[u]] == 1) lab[u] += d; }
        for (int b = n + 1; b <= n_x; b++) if (st[b] == b) { if (S[b] == 0) lab[b] += d * 2; else if (S[b] == 1) lab[b] -= d * 2; }
        q.clear();
        for (int x = 1; x <= n_x; x++) if (st[x] == x && slack[x] && st[slack[x]] != x && e_delta(g[slack[x]][x]) == 0)
            if (on_found_edge(g[slack[x]][x])) return true;
        for (int b = n + 1; b <= n_x; b++) if (st[b] == b && S[b] == 1 && lab[b] == 0) expand_blossom(b);
    }
    return false;
}
long long solve() {
    fill(match_ + 1, match_ + n + 1, 0); n_x = n; int wmax = 0;
    for (int u = 1; u <= n; u++) { st[u] = u; flower[u].clear(); }
    for (int u = 1; u <= n; u++) for (int v = 1; v <= n; v++) {
        flower_from[u][v] = (u == v ? u : 0); wmax = max(wmax, g[u][v].w); }
    for (int u = 1; u <= n; u++) lab[u] = wmax;             // 쌍대 초기화
    while (matching()) {}                                   // 증가 경로가 없을 때까지
    long long tot = 0;
    for (int u = 1; u <= n; u++) if (match_[u] && match_[u] < u) tot += g[u][match_[u]].w;
    return tot;
}

입력 세팅: n을 정하고 각 간선 $$(u,v,w)$$ 에 대해 g[u][v] = {u,v,w}, g[v][u] = {v,u,w}를 채운 뒤 solve() 호출. 없는 간선은 w = 0.

단계(phase) 요약

matching(): 한 번의 원시–쌍대 위상. even 정점들에서 빡빡한 간선을 탐색 → 트리 확장 / 블로섬 수축(add_blossom) / 증가(augment).
막히면 $\delta$ 를 계산해 쌍대 lab을 조정(even: $-\delta$ , inner: $+\delta$ , 블로섬: $\pm 2\delta$ )하고, 새로 빡빡해진 간선을 처리하거나 $$z=0$$ 이 된 블로섬을 팽창(expand_blossom).
solve()가 이 위상을 증가 경로가 없어질 때까지 반복.

Lesson 심화: 완전 매칭·최소화·정밀도·함정 선택 8m

변형과 모델링

최대 가중 vs 최대 가중 완전 매칭

위 구현은 최대 가중 매칭(매칭 크기 무관, 가중치 합 최대)이다. 완전 매칭을 강제하려면(모든 정점을 짝지어야 함), 없는 간선에 아주 작은(매우 음수인) 가중치 대신 큰 상수 $$C$$ 를 모든 간선에 더해 매칭이 최대 크기로 커지도록 유도한다. 예: 모든 실제 간선 가중치에 $$+C$$ ( $$C$$ 가 충분히 크면 알고리즘이 간선을 최대한 많이 쓰는 쪽을 선호)하고, 완전 그래프로 만들되 원래 없던 간선은 $$+C$$ 만 부여. 최종 답에서 $C \times (n/2)$ 를 빼면 실제 완전 매칭 가중치.

최소 가중 완전 매칭

부호 반전으로 최대화로 바꾼다: $w'(e) = W_{\max} - w(e)$ 또는 $$w'(e) = -w(e)$$ 후 완전 매칭 강제. 구현이 정수·비음수 가중치를 가정하면 상수 이동으로 비음수화한다.

정수 가중치와 정밀도

이 알고리즘은 정수 가중치에서 정확하다. e_delta가 $$2$$ 를 곱하는 형태라 내부적으로 짝수 스케일을 쓰므로, 실수 가중치는 정수로 스케일링(예: $\times 2$ 후 반올림)해 넣는 것이 안전하다. 부동소수로 그대로 돌리면 $\delta$ 계산의 미세 오차가 무한 루프/오답을 부른다.

크기 제한

$$O(n^3)$$ · $$O(n^2)$$ 메모리(인접 행렬)라 $$n$$ 이 수백을 넘으면 무겁다. 희소하고 이분이면 헝가리안/MCMF가, 이분이 아니고 크면 문제 특수 구조를 찾아야 한다.

엣지 케이스와 흔한 버그

인접 행렬 & 1-인덱스: 정점 번호 1..n, g[u][v]에 대칭으로 채우기. 0-인덱스나 인접 리스트로 바꾸려다 flower_from/st 관리가 깨지기 쉬우니 원형 그대로 사용.
없는 간선 = w 0: g[u][v].w > 0 조건으로 간선 유무를 판단하므로, 가중치 0인 실제 간선을 쓰려면 모든 가중치를 $$+1$$ 이동해 0을 피하거나 코드의 간선 유무 판정을 별도 플래그로 바꿔야 한다. (이 함정이 매우 흔하다.)
쌍대 초기화: lab[u] = wmax(최대 간선 가중치)로 시작해야 여유가 비음수로 유지된다. 0으로 두면 즉시 깨진다.
n_x 범위: 블로섬을 만들면 가상 정점이 $n+1 \dots n_x$ 로 늘어난다. MAXN은 $$2n$$ 이상이어야(블로섬 중첩) 배열 오버런이 안 난다. $n\le 500$ 이면 MAXN=505로는 부족할 수 있으니 여유 있게(예: 2*n+5) 잡아라.
블로섬 수축/팽창 순서: add_blossom의 flower 구성(짝수 인덱스 outer, 홀수 inner)과 get_pr의 회전 로직이 augment의 경로 복원과 맞물린다. 이 부분을 임의로 수정하면 미묘하게 틀린다.
검증 필수: 구현이 복잡하니 반드시 작은 랜덤 그래프에서 완전탐색과 대조하라(완전 그래프 $n\le 8$ 에서 수백 케이스). 삼각형·5-사이클 등 홀수 구조를 반드시 포함.
오버플로: 가중치 합이 크면 long long으로 누적(e_delta의 int는 개별 여유용이나, 큰 가중치면 int 오버플로 주의 — 필요시 전체를 long long화).

가중 일반 매칭은 매칭 이론의 정점이다. 이론(에드몬즈 LP·쌍대)과 코드를 모두 완벽히 재현하기 어렵기 때문에, 검증된 참조 구현을 그대로 쓰고 각 위상이 무엇을 하는지 이해하는 것이 실전 전략이다.

Practice problem 결투의 짝짓기 선택 25m

R00695

결투의 짝짓기

힌트를 열기 전에 상태와 전이를 먼저 찾아보세요.

다이아몬드 II 지금 풀기

자연어 제약	절 / 함의
$\(a\)$ 또는 $\(b\)$ 중 적어도 하나 참	$(a \lor b)$
$\(a\)$ 이면 $\(b\)$	$(\lnot a \lor b)$
$\(a\)$ 와 $\(b\)$ 중 최대 하나만 참	$(\lnot a \lor \lnot b)$
$\(a\)$ 와 $\(b\)$ 는 같은 값	$(a\lor\lnot b)\land(\lnot a\lor b)$
$\(a\)$ 와 $\(b\)$ 는 다른 값(XOR)	$(a\lor b)\land(\lnot a\lor\lnot b)$
$\(a\)$ 를 참으로 강제	$\lnot a \to a$

문제	모델링
이분 매칭	$s\to$ 왼쪽(용량1), 왼쪽 $\to$ 오른쪽(용량1), 오른쪽 $\to t$ (용량1)
정점 용량 $\(cap(v)\)$	정점을 $v_{in}, v_{out}$ 로 쪼개고 $v_{in}\to v_{out}$ 에 용량 $\(cap(v)\)$
정점-서로소 경로 수	위 정점분할 + 각 정점 용량 1
간선-서로소 경로 수	각 간선 용량 1, 최대 유량
프로젝트 선택(최대 이익)	최대 이익 $= \sum(\text{양의 이익}) - \min\text{컷}$

상황	권장
$n\times n$ 밀집 완전 매칭	헝가리안 $\(O(n^3)\)$
희소 이분 그래프, 완전 매칭 아님	MCMF
정점/간선 용량 등 일반 제약	MCMF
매우 큰 $\(n\)$ 이지만 특수 구조	문제별

항목	값
시간	$\(O(V + E)\)$
공간	$\(O(V + E)\)$