Dominator Tree
정의
유향 그래프와 시작점 s 가 주어졌을 때, 정점 u 가 정점 v 를 dominate 한다는 것은 s 에서 v 로 가는 모든 경로가 반드시 u 를 지난다 는 뜻. Dominator Tree 는 모든 정점에 대해 immediate dominator (가장 가까운 dominator) 를 부모로 둔 트리.
컴파일러 (LLVM, GCC 의 SSA 분석), 정적 분석에서 핵심 도구. PS 에서는 “이 정점을 제거하면 도달 불가능해지는 정점들” 같은 카운팅이나 DAG 위 경로 / 비용 계산 에 등장.
문제 상황과 동기
주어진 유향 그래프에서 출발점 s 에서 정점 v 까지 모든 경로가 반드시 지나는 정점 (dominator) 을 빠르게 찾고 싶다. naive 하게는 각 정점을 제거한 뒤 BFS / DFS 로 도달 가능 여부를 확인하면 O(V (V + E)).
핵심 통찰: DFS tree 위에서 semidominator 라는 보조 개념을 도입하면 단 한 번의 DFS 와 path compression 만으로 모든 정점의 immediate dominator 를 O((V+E) α(V)) ~ O((V+E) log V) 에 구할 수 있다. DAG 인 경우 더 간단하게 DP + LCA 로 O((V+E) log V).
컴파일러 CFG (Control Flow Graph) 최적화, 루프 분석, phi 함수 배치에서 필수이며, PS 에서는 “관문 (gateway) 정점”, “제거 시 도달 불가능해지는 서브그래프” 같은 문제에 등장.
시각화
핵심 아이디어 (Lengauer-Tarjan)
DFS 트리 + semidominator 라는 보조 개념으로 O((V+E) α(V)) 또는 O((V+E) log V).
1. s 에서 DFS, 정점에 DFS 번호 부여
2. 각 정점 v 의 semidominator sdom[v] :
= min(dfs_num(w)) such that exists w -> v 경로에서 v 보다 dfs_num 큰 정점들만 거침
3. semidominator 로 부터 immediate dominator 도출 (sdom 의 path compression)DAG 라면 간단한 dp + LCA 로 O((V+E) log V) 정도로 가능 (mhy908 블로그 참고). 일반 유향 그래프는 Lengauer-Tarjan 또는 Baba 의 O((V+E) log V) 변형.
작은 예시 (DAG)
DAG:
s -> a -> c
\-> b -/
도달 경로:
s: []
a: s
b: s
c: s (a, b 둘 다 지나도록 할 수 있음)
dominator:
a 의 모든 경로는 s 를 지남 → dom[a] = s
b 의 모든 경로는 s 를 지남 → dom[b] = s
c 로 가는 경로: s-a-c, s-b-c → 공통은 s → dom[c] = s
트리:
s
├─ a
├─ b
└─ cDAG 에서는 v 로 들어오는 모든 간선의 끝점들의 dominator LCA = dom[v].
복잡도
| 알고리즘 | 시간 |
|---|---|
| naive (각 정점 제거 + reachability) | O(V (V+E)) |
| Lengauer-Tarjan | O((V+E) α(V)) ~ O((V+E) log V) |
| DAG 전용 (DP + LCA) | O((V+E) log V) |
응용
1. 정점 / 간선의 critical 분석
v 를 dominate 하는 정점 = 제거 시 v 도달 불가능. dominator tree 의 조상 = critical 정점.
2. 컴파일러 SSA / Loop 분석
CFG (Control Flow Graph) 에서 loop header 식별, phi 함수 위치 결정.
3. PS 응용
- “출발점에서 모든 곳으로 가는데 반드시 지나야 하는 관문 정점들”
- “정점 v 에 도달 가능한 정점 수” = dominator tree 의 서브트리 크기
구현
DAG 전용 (DP + LCA)
DAG 에서는 위상 정렬 + DP 로 간단히 계산 가능:
// O((V+E) log V), DAG 에서만 동작
#include <vector>
#include <algorithm>
using namespace std;
vector<int> dominator_tree_dag(int n, int s, const vector<vector<int>>& g) {
// dom[v] = v 의 immediate dominator
vector<int> dom(n, -1);
vector<int> indeg(n);
for (int u = 0; u < n; u++) {
for (int v : g[u]) indeg[v]++;
}
// 위상 정렬 + DP
vector<int> q;
dom[s] = s;
q.push_back(s);
for (size_t i = 0; i < q.size(); i++) {
int u = q[i];
for (int v : g[u]) {
if (dom[v] == -1) {
// v 의 첫 진입: dom[v] = u
dom[v] = u;
} else {
// v 로 두 번째 이상: LCA(dom[v], u)
// naive: 두 정점의 공통 조상 찾기
auto path_to_root = [&](int x) {
vector<int> p;
while (x != s) { p.push_back(x); x = dom[x]; }
p.push_back(s);
return p;
};
auto p1 = path_to_root(dom[v]);
auto p2 = path_to_root(u);
reverse(p1.begin(), p1.end());
reverse(p2.begin(), p2.end());
int lca = s;
for (size_t j = 0; j < min(p1.size(), p2.size()); j++) {
if (p1[j] == p2[j]) lca = p1[j];
else break;
}
dom[v] = lca;
}
if (--indeg[v] == 0) q.push_back(v);
}
}
return dom;
}일반 그래프 (Lengauer-Tarjan)
일반 유향 그래프는 Lengauer-Tarjan 알고리즘 필요. 코드가 길어 여기서는 pseudocode 로 제시:
Lengauer-Tarjan:
1. DFS 로 정점 번호 부여, parent 트리 구성
2. DFS 역순으로 각 v 에 대해 semidominator 계산:
sdom[v] = min(dfs_num(u)) for all incoming edges (w, v)
where w -> ... -> v 경로에서 v 보다 dfs_num 큰 정점만 거침
3. Union-Find / path compression 으로 sdom 에서 idom 도출
4. 마지막 pass 로 idom 을 확정
복잡도: O((V+E) α(V)) (union-find 사용)
O((V+E) log V) (balanced tree 사용)검증된 구현은 koosaga, jinhan814 블로그 참고.
함정
1. 시작점 외 정점은 무시
s 에서 도달 불가능한 정점은 트리에 포함되지 않음. 전처리로 도달 가능한 것만 추출.
2. DAG 전용 알고리즘은 일반 그래프에 못 씀
사이클이 있는 경우 단순 DP 가 동작하지 않음. Lengauer-Tarjan 필요.
3. 구현 검증
Lengauer-Tarjan 은 디버깅이 까다롭다. brute force (각 정점 제거 후 BFS) 로 작은 케이스 비교 필수.
BOJ 연습 문제
DAG
| 번호 | 제목 | 링크 |
|---|---|---|
| BOJ 7777 | 병원 | kokoa-lab |
| BOJ 19335 | Increasing Costs | kokoa-lab |
일반
| 번호 | 제목 | 링크 |
|---|---|---|
| BOJ 20174 | Ink Mix | kokoa-lab |
| BOJ 25424 | School Road | kokoa-lab |
다른 출처 연습 문제
| 출처 | 제목 | 링크 |
|---|---|---|
| Library Checker | Dominator Tree | https://judge.yosupo.jp/problem/dominatortree |
💬 댓글