[Baekjoon] 1734 – 교통체계
📖 문제 이해하기
이 문제는 그래프 이론에서 핵심적인 개념인 절단점(Articulation Point)과 브리지(Bridge)를 활용하여 그래프의 연결성을 판단하는 문제입니다.
문제에서는 N개의 도시와 E개의 양방향 도로로 이루어진 연결된 그래프가 주어집니다. 우리는 두 가지 유형의 질문에 답해야 합니다:
- 특정 도로를 제거했을 때, 두 도시 A와 B가 여전히 연결되어 있는가?
- 특정 도시와 연결된 모든 도로를 제거했을 때, 두 도시 A와 B가 여전히 연결되어 있는가?
예를 들어, 도시 1-2-3-4가 일직선으로 연결된 그래프에서 도시 2와 3을 잇는 도로를 제거하면, 도시 1에서 도시 4로 갈 수 없게 됩니다. 반면 도시가 삼각형을 이루고 있다면, 어떤 한 도로를 제거해도 여전히 연결성이 유지됩니다.
핵심 제약사항은 N이 최대 100,000개, 질문이 최대 300,000개라는 점입니다. 각 질문마다 그래프 탐색을 수행한다면 시간 초과가 발생할 것입니다.
🧠 순진한 접근법과 그 한계
처음 이 문제를 마주한다면, 가장 직관적인 해결법은 각 질문마다 실제로 해당 요소를 제거한 후 DFS나 BFS를 통해 연결성을 확인하는 것입니다.
유형 1 질문의 경우, 특정 간선을 제거한 그래프에서 A에서 B로의 경로가 존재하는지 확인하면 됩니다. 유형 2 질문의 경우, 특정 정점과 연결된 모든 간선을 제거한 후 동일한 작업을 수행하면 됩니다.
하지만 이 접근법의 문제는 시간 복잡도입니다. 각 질문마다 O(N + E)의 그래프 탐색이 필요하고, 최대 300,000개의 질문이 있으므로 전체 시간 복잡도는 O(Q × (N + E))가 됩니다. N과 E가 각각 100,000, 500,000에 달할 수 있고 Q가 300,000이므로, 이는 약 2400억 번의 연산을 의미합니다. 이는 일반적인 시간 제한 내에서는 불가능한 수준입니다.
더 큰 문제는 매 질문마다 동일한 구조적 특성을 반복해서 계산한다는 점입니다. 그래프의 연결성에 중요한 역할을 하는 요소들—즉, 제거했을 때 그래프를 분리시키는 간선과 정점들—은 그래프가 주어지는 순간 결정됩니다. 이러한 정보를 미리 전처리해 둔다면 각 질문에 대해 훨씬 효율적으로 답할 수 있을 것입니다.
💡 핵심 아이디어의 발견
순진한 접근법의 한계를 극복하는 열쇠는 그래프의 구조적 특성을 사전에 분석하는 것입니다. 연결된 그래프에서 특정 요소를 제거했을 때 연결성이 깨지는지 여부는, 그 요소가 그래프의 연결성에 얼마나 중요한 역할을 하는지에 달려 있습니다.
그래프 이론에서는 이러한 중요한 요소들을 정확히 정의하고 있습니다. 브리지(Bridge)는 제거했을 때 그래프의 연결 성분의 개수를 증가시키는 간선입니다. 절단점(Articulation Point)은 제거했을 때 그래프의 연결 성분의 개수를 증가시키는 정점입니다.
핵심 통찰은 다음과 같습니다. 유형 1 질문에서, 제거하려는 간선이 브리지가 아니라면 그래프의 연결성은 유지됩니다. 유형 2 질문에서, 제거하려는 정점이 절단점이 아니라면 그래프의 연결성은 유지됩니다.
하지만 브리지이거나 절단점인 경우에도, 질문에서 언급된 두 정점 A와 B가 여전히 연결될 수 있습니다. 이는 A와 B가 제거된 요소와 관련하여 같은 연결 성분에 속해 있을 때 발생합니다.
이 문제를 해결하기 위해 블록-컷 트리(Block-Cut Tree)라는 보조 그래프를 구성합니다. 이 트리에서는 원래 그래프의 각 이중 연결 성분을 하나의 블록 노드로 표현하고, 절단점들을 별도의 노드로 표현합니다. 이 트리 구조를 이용하면 두 정점 간의 관계를 효율적으로 분석할 수 있습니다.
📘 절단점과 브리지 찾기
절단점과 브리지를 찾는 것은 타잔(Tarjan)의 알고리즘을 사용합니다. 이 알고리즘은 DFS 트리를 구성하면서 각 정점의 방문 시간과 back edge를 통해 도달할 수 있는 가장 이른 정점의 시간을 추적합니다. 이 정보를 바탕으로 절단점과 브리지를 선형 시간에 찾을 수 있습니다.
📘 블록-컷 트리
블록-컷 트리는 원래 그래프의 구조를 트리 형태로 변환한 것입니다. 각 이중 연결 성분(biconnected component)은 하나의 블록 노드가 되고, 절단점들은 컷 노드가 됩니다. 이 트리에서 두 정점 간의 경로는 원래 그래프에서의 연결성을 정확히 반영합니다.
🔍 알고리즘 상세 과정
이제 구체적인 예시를 통해 알고리즘의 동작 과정을 살펴보겠습니다. 다음과 같은 그래프가 있다고 가정합시다.
1 - 2 - 3
|
4이 그래프에서 정점 2는 절단점입니다. 정점 2를 제거하면 {1}, {3}, {4}로 분리되기 때문입니다. 또한 간선 (1,2), (2,3), (2,4)는 모두 브리지입니다.
1단계: 절단점과 브리지 찾기
DFS를 시작하여 각 정점의 dfs_num(방문 시간)과 dfs_low(back edge로 도달 가능한 가장 이른 시간)를 계산합니다. 정점 1부터 시작하면,
- 정점 1 방문:
dfs_num[1] = 1, dfs_low[1] = 1 - 정점 2 방문:
dfs_num[2] = 2, dfs_low[2] = 2 - 정점 3 방문 (2의 첫 번째 자식):
dfs_num[3] = 3, dfs_low[3] = 3 - 정점 3에서 되돌아와서,
dfs_low[3] = 3 > dfs_num[2] = 2이므로 간선 (2,3)은 브리지 - 정점 4 방문 (2의 두 번째 자식):
dfs_num[4] = 4, dfs_low[4] = 4 - 정점 4에서 되돌아와서,
dfs_low[4] = 4 > dfs_num[2] = 2이므로 간선 (2,4)도 브리지 - 정점 2는 두 개의 자식을 가지고 있고 각각의
dfs_low가dfs_num[2]보다 크므로 절단점
2단계: 이중 연결 성분 찾기
DFS 과정에서 스택을 이용해 이중 연결 성분을 찾습니다. 절단점을 만날 때마다 스택에서 해당 성분의 간선들을 꺼내어 하나의 블록을 형성합니다.
- 블록 1: {1, 2} (간선 (1,2)로 구성)
- 블록 2: {2, 3} (간선 (2,3)으로 구성)
- 블록 3: {2, 4} (간선 (2,4)로 구성)
3단계: 블록-컷 트리 구성
각 블록을 새로운 노드로 만들고, 원래 정점들과 연결합니다.
- 원래 정점: 1, 2, 3, 4
- 블록 노드: 5 (블록 1), 6 (블록 2), 7 (블록 3)
- 연결 관계:
- 정점 1은 블록 5와 연결
- 정점 2는 블록 5, 6, 7과 모두 연결 (절단점이므로)
- 정점 3은 블록 6과 연결
- 정점 4는 블록 7과 연결
블록-컷 트리의 최종 모습
1 - 5 - 2 - 6 - 3
|
7
|
44단계: LCA 전처리
블록-컷 트리에서 임의의 두 정점 간 LCA를 빠르게 구하기 위해 이진 리프팅을 준비합니다. 정점 1을 루트로 하여 각 정점의 깊이와 2^k번째 조상을 미리 계산해 둡니다.
5단계: 질문 처리
이제 각 질문을 O(log N) 시간에 처리할 수 있습니다.
예를 들어, “간선 (2,3)을 제거했을 때 정점 1과 정점 4가 연결되어 있는가?”라는 질문이 있다면:
- 간선 (2,3)이 브리지인지 확인 → 브리지임
- 정점 1과 4가 같은 쪽에 있는지 확인 → 블록-컷 트리에서 1과 4의 LCA는 2이고, 제거되는 간선의 더 깊은 쪽은 정점 3
lca(1, 3) = 2 ≠ 3이고lca(4, 3) = 2 ≠ 3이므로, 1과 4 모두 정점 3 쪽에 있지 않음- 따라서 답은 “yes”
💻 소스 코드
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 600000
#define LOG 19
int N, E, Q, T, A, B, C, G1, G2, u, v;
int dfs_num[MAX_N+1], dfs_low[MAX_N+1], depth[MAX_N+1]; <em>// DFS 번호, Low 값, 블록-컷 트리에서의 깊이</em>
int parent[MAX_N+1][LOG]; <em>// 이진 리프팅을 위한 조상 테이블</em>
int timer = 0; <em>// DFS 방문 시간을 추적하는 전역 타이머</em>
bool AP[MAX_N+1]; <em>// 각 정점이 절단점인지 여부를 저장</em>
unordered_map<int,vector<int>> G, BG; <em>// 원래 그래프 G와 블록-컷 트리 BG</em>
vector<pair<int,int>> ST; <em>// 이중 연결 성분을 찾기 위한 간선 스택</em>
vector<unordered_set<int>> bccs; <em>// 각 이중 연결 성분을 저장</em>
set<pair<int,int>> BR; <em>// 브리지들을 저장하는 집합</em>
<em>// 타잔 알고리즘을 이용해 절단점과 브리지, 이중 연결 성분을 찾는 함수</em>
void findBccs(int node, int p) {
dfs_num[node] = dfs_low[node] = ++timer; <em>// 현재 노드의 방문 시간 설정</em>
int child = 0; <em>// 루트 노드의 자식 수를 세기 위한 변수</em>
for (auto & x : G[node]) { <em>// 현재 노드의 모든 인접 노드 탐색</em>
if (x == p) continue; <em>// 부모 노드는 건너뛰기</em>
if (dfs_num[x] == -1) { <em>// 아직 방문하지 않은 노드라면</em>
child++;
ST.push_back({node, x}); <em>// 현재 간선을 스택에 추가</em>
findBccs(x, node); <em>// 재귀적으로 DFS 수행</em>
dfs_low[node] = min(dfs_low[node], dfs_low[x]); <em>// Low 값 업데이트</em>
<em>// 절단점 조건 확인: 루트가 아닌 경우 dfs_low[x] >= dfs_num[node]</em>
<em>// 루트인 경우 자식이 2개 이상</em>
if ((p != -1 && dfs_low[x] >= dfs_num[node]) || (p == -1 && child > 1)) {
AP[node] = true; <em>// 현재 노드를 절단점으로 표시</em>
unordered_set<int> bcc; <em>// 새로운 이중 연결 성분</em>
<em>// 스택에서 간선들을 꺼내어 이중 연결 성분 구성</em>
while(true) {
tie(u, v) = ST.back();
ST.pop_back();
bcc.insert(u);
bcc.insert(v);
if (u == node && v == x) break; <em>// 현재 간선까지 처리 완료</em>
}
bccs.push_back(bcc); <em>// 완성된 이중 연결 성분 저장</em>
}
<em>// 브리지 조건 확인: dfs_low[x] > dfs_num[node]</em>
if (dfs_low[x] > dfs_num[node]) {
BR.insert({min(x, node), max(x, node)}); <em>// 브리지로 등록</em>
}
} else {
<em>// 이미 방문한 노드인 경우 (back edge 또는 forward edge)</em>
if (dfs_num[x] < dfs_num[node]) { <em>// back edge인 경우</em>
dfs_low[node] = min(dfs_low[node], dfs_num[x]); <em>// Low 값 업데이트</em>
ST.push_back({node, x}); <em>// 스택에 간선 추가</em>
}
}
}
}
<em>// 블록-컷 트리에서 각 노드의 깊이를 설정하고 부모 관계를 구성하는 함수</em>
void setDepth(int node, int d) {
depth[node] = d; <em>// 현재 노드의 깊이 설정</em>
for (auto & x : BG[node]) { <em>// 모든 인접 노드 탐색</em>
if (depth[x] == -1) { <em>// 아직 깊이가 설정되지 않은 노드라면</em>
parent[x][0] = node; <em>// 첫 번째 조상(2^0 = 1번째 조상)을 현재 노드로 설정</em>
setDepth(x, d + 1); <em>// 재귀적으로 깊이 설정</em>
}
}
}
<em>// 이진 리프팅을 이용해 두 노드의 최소 공통 조상(LCA)을 찾는 함수</em>
int lca(int a, int b) {
if (depth[a] > depth[b]) swap(a, b); <em>// b가 더 깊은 노드가 되도록 조정</em>
<em>// b를 a와 같은 깊이까지 끌어올리기</em>
for (int i = LOG-1; i >= 0; --i) {
if (depth[b] - (1 << i) >= depth[a]) {
b = parent[b][i];
}
}
if (a == b) return a; <em>// 같은 노드라면 그 노드가 LCA</em>
<em>// 두 노드를 동시에 위로 올리면서 LCA 찾기</em>
for (int i = LOG-1; i >= 0; --i) {
if (parent[a][i] != parent[b][i]) {
a = parent[a][i];
b = parent[b][i];
}
}
return parent[a][0]; <em>// 최종 LCA 반환</em>
}
<em>// 블록-컷 트리에서 두 노드 간의 거리를 계산하는 함수</em>
int getDist(int a, int b) {
int l = lca(a, b); <em>// 두 노드의 LCA 계산</em>
return depth[a] + depth[b] - 2 * depth[l]; <em>// 거리 공식 적용</em>
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
<em>// 배열 초기화</em>
memset(dfs_num, -1, sizeof(dfs_num)); <em>// 모든 노드를 미방문으로 설정</em>
memset(depth, -1, sizeof(depth)); <em>// 모든 노드의 깊이를 -1로 초기화</em>
memset(parent, 0, sizeof(parent)); <em>// 부모 테이블 초기화</em>
memset(AP, false, sizeof(AP)); <em>// 절단점 배열 초기화</em>
cin >> N >> E;
<em>// 그래프 입력 처리</em>
for (int i = 0; i < E; ++i) {
cin >> u >> v;
G[u].push_back(v); <em>// 양방향 그래프이므로</em>
G[v].push_back(u); <em>// 양쪽 모두에 간선 추가</em>
}
<em>// 절단점, 브리지, 이중 연결 성분 찾기</em>
findBccs(1, -1); <em>// 노드 1부터 DFS 시작</em>
<em>// 스택에 남은 간선들로 마지막 이중 연결 성분 구성</em>
if (!ST.empty()) {
unordered_set<int> bcc;
while(!ST.empty()) {
tie(u, v) = ST.back();
ST.pop_back();
bcc.insert(u);
bcc.insert(v);
}
bccs.push_back(bcc);
}
<em>// 블록-컷 트리 구성</em>
for (int i = 0; i < bccs.size(); ++i) {
int block = N + 1 + i; <em>// 블록 노드의 번호는 N+1부터 시작</em>
for (auto & x : bccs[i]) {
BG[x].push_back(block); <em>// 원래 노드와 블록 노드 연결</em>
BG[block].push_back(x); <em>// 양방향 연결</em>
}
}
<em>// 블록-컷 트리에서 깊이 설정 및 부모 관계 구성</em>
setDepth(1, 0); <em>// 노드 1을 루트로 설정</em>
int size = N + bccs.size(); <em>// 전체 노드 수 (원래 노드 + 블록 노드)</em>
<em>// 이진 리프팅을 위한 조상 테이블 구성</em>
for (int j = 1; j < LOG; ++j) {
for (int i = 1; i <= size; ++i) {
parent[i][j] = parent[parent[i][j-1]][j-1]; <em>// 2^j번째 조상 계산</em>
}
}
cin >> Q;
while(Q--) {
cin >> T;
if (T == 1) { <em>// 유형 1: 간선 제거 질문</em>
cin >> A >> B >> G1 >> G2;
<em>// 제거할 간선이 브리지가 아니라면 연결성 유지</em>
if (BR.find({min(G1,G2), max(G1,G2)}) == BR.end()) {
cout << "yes" << "\n";
continue;
}
<em>// 브리지인 경우, A와 B가 같은 쪽에 있는지 확인</em>
int target = depth[G1] > depth[G2] ? G1 : G2; <em>// 더 깊은 쪽 선택</em>
bool a = lca(A, target) == target; <em>// A가 target 쪽에 있는지</em>
bool b = lca(B, target) == target; <em>// B가 target 쪽에 있는지</em>
if (a == b) { <em>// 같은 쪽에 있다면 연결 가능</em>
cout << "yes" << "\n";
} else {
cout << "no" << "\n";
}
} else { <em>// 유형 2: 정점 제거 질문</em>
cin >> A >> B >> C;
<em>// 제거할 정점이 절단점이 아니라면 연결성 유지</em>
if (!AP[C]) {
cout << "yes" << "\n";
continue;
}
<em>// 절단점인 경우, A-B 경로가 C를 지나는지 확인</em>
int ab = getDist(A, B); <em>// A-B 직접 거리</em>
int ac = getDist(A, C); <em>// A-C 거리</em>
int bc = getDist(B, C); <em>// B-C 거리</em>
if (ac + bc != ab) { <em>// C를 거치지 않는 경로가 존재</em>
cout << "yes" << "\n";
} else { <em>// 모든 A-B 경로가 C를 지남</em>
cout << "no" << "\n";
}
}
}
return 0;
}🔁 대안적 접근법
이 문제는 **유니온-파인드(Union-Find)**를 이용한 동적 연결성 문제로도 접근할 수 있습니다. 하지만 이 경우 간선이나 정점을 제거하는 연산이 필요한데, 일반적인 유니온-파인드는 합치기 연산만 지원하므로 분리 가능 유니온-파인드 같은 고급 자료구조가 필요합니다.
또 다른 접근법은 오프라인 쿼리 처리입니다. 모든 질문을 미리 읽어들인 후, 제거될 요소들을 미리 제거한 상태에서 역순으로 처리하는 방법입니다. 이는 구현이 복잡하지만 일부 경우에 더 효율적일 수 있습니다.
하지만 이 문제의 경우, 절단점과 브리지를 이용한 접근법이 가장 직관적이고 효율적입니다. 전처리 시간 O(N + E), 각 질문당 O(log N)으로 전체 시간 복잡도가 O(N + E + Q log N)이 되어 주어진 제약조건을 충분히 만족합니다.
📌 핵심 교훈과 요약
이 문제는 그래프 이론의 핵심 개념들이 실제 문제 해결에 어떻게 적용되는지 보여주는 훌륭한 예시입니다. 단순히 알고리즘을 암기하는 것이 아니라, 문제의 본질을 파악하고 적절한 자료구조와 알고리즘을 선택하는 것이 중요합니다.
특히 전처리를 통한 최적화의 중요성을 잘 보여줍니다. 각 질문마다 독립적으로 계산하는 대신, 그래프의 구조적 특성을 미리 분석해 두면 훨씬 효율적으로 문제를 해결할 수 있습니다.
블록-컷 트리라는 보조 자료구조를 통해 복잡한 그래프 구조를 단순한 트리로 변환하여 분석하는 것도 중요한 기법입니다. 이는 그래프 문제를 트리 문제로 환원하여 더 쉽고 효율적으로 해결할 수 있게 해줍니다.