강연결 성분 (SCC) 과 그래프 축소 기법
유향 그래프에서 사이클이 존재하는 경우, 경로 탐색 문제나 최대权值 합산 문제 등을 해결하기 위해 그래프의 구조를 단순화할 필요가 있습니다. 이때강연결 성분 (Strongly Connected Component, SCC) 개념을 활용하여 사이클을 하나의 노드로 축소하면, 원래 그래프를비순환 유향 그래프 (DAG)로 변환할 수 있습니다.
본 문서에서는 타잔 (Tarjan) 알고리즘을 사용하여 SCC 를 추출하고, 이를 바탕으로 그래프를 축소한 뒤 동적 계획법을 적용하는 과정까지 다룹니다.
타잔 알고리즘의 핵심 원리
타잔 알고리즘은 깊이 우선 탐색 (DFS) 을 기반으로 하여 각 노드의 탐색 순서와 역추적 가능한 최소 순서를 비교하여 SCC 를 판별합니다. 이를 위해 다음 두 가지 값과 스택 구조를 유지합니다.
- 탐색 순서 (discoveryTime): DFS 과정에서 노드가 방문된 시점을 기록하는 타임스탬프입니다.
- 최소 도달 순서 (lowLink): 해당 노드에서 출발하여 트리 간선이나 백 에지를 통해 도달할 수 있는 노드 중 가장 빠른 탐색 순서입니다.
- 재귀 스택 (recursionStack): 현재 DFS 경로상에 있으며 아직 SCC 로 확정되지 않은 노드들을 저장합니다.
DFS 진행 중 어떤 노드 u에 대해 discoveryTime[u] == lowLink[u] 조건이 성립하면, u는 해당 강연결 성분의 루트 노드가 됩니다. 이때 스택에서 u를 만날 때까지_pop_된 노드들이 하나의 SCC 를 구성합니다.
알고리즘 구현 상세
다음 코드는 타잔 알고리즘을 구현한 예시입니다. 변수명은 가독성을 위해 변경하였으며, 논리적 흐름은 원래 알고리즘을 따릅니다.
#include <vector>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;
const int MAX_NODES = 10005;
// 그래프 구조체
struct Graph {
int nodeCount;
int weights[MAX_NODES];
vector<int> adj[MAX_NODES];
};
// 전역 변수 선언
Graph originalGraph, dagGraph;
int discoverTime[MAX_NODES], lowLink[MAX_NODES];
int sccId[MAX_NODES], sccCount;
bool onStack[MAX_NODES];
stack<int> recursionStack;
int timer;
// 타잔 알고리즘 핵심 함수
void findSCC(int node) {
discoverTime[node] = lowLink[node] = ++timer;
recursionStack.push(node);
onStack[node] = true;
for (int neighbor : originalGraph.adj[node]) {
if (discoverTime[neighbor] == 0) {
// 아직 방문하지 않은 자식 노드
findSCC(neighbor);
lowLink[node] = min(lowLink[node], lowLink[neighbor]);
} else if (onStack[neighbor]) {
// 스택에 있는 조상 노드 (백 에지)
lowLink[node] = min(lowLink[node], discoverTime[neighbor]);
}
}
// SCC 루트 노드 발견
if (discoverTime[node] == lowLink[node]) {
sccCount++;
while (true) {
int top = recursionStack.top();
recursionStack.pop();
onStack[top] = false;
sccId[top] = sccCount;
if (top == node) break;
}
}
}
그래프 축소 (Condensation)
SCC 추출이 완료되면, 각 SCC 를 하나의 슈퍼 노드로 취급하여 새로운 그래프를 구축합니다. 이때 원래 그래프의 간선 중 서로 다른 SCC 를 연결하는 간선만을 선택해야 하며, 자기 자신으로 향하는 간선 (Self-loop) 은 제거해야 합니다.
축소된 그래프는 DAG 구조를 가지므로 위상 정렬을 통해 순서를 확보한 뒤 동적 계획법을 적용할 수 있습니다.
// 그래프 축소 및 가중치 합산
void buildDAG() {
dagGraph.nodeCount = sccCount;
// 각 SCC 에 속한 노드들의 가중치 합산
for (int i = 1; i <= originalGraph.nodeCount; ++i) {
dagGraph.weights[sccId[i]] += originalGraph.weights[i];
}
// 간선 재구성 (중복 제거 필요시 set 활용 가능)
for (int u = 1; u <= originalGraph.nodeCount; ++u) {
for (int v : originalGraph.adj[u]) {
if (sccId[u] != sccId[v]) {
dagGraph.adj[sccId[u]].push_back(sccId[v]);
}
}
}
}
DAG 에서의 동적 계획법
축소된 그래프에서 최대 가중치 경로를 찾기 위해서는 위상 정렬 순서대로 노드를 순회하며 DP 값을 갱신합니다. 각 노드의 DP 값은 해당 노드의 가중치와 이전 노드들로부터 전달된 최대 값의 합으로 결정됩니다.
int inDegree[MAX_NODES];
int topoOrder[MAX_NODES];
int dpValue[MAX_NODES];
// 위상 정렬 수행
void performTopologicalSort() {
int head = 0, tail = 0;
// 진입차수 계산
for (int i = 1; i <= dagGraph.nodeCount; ++i) {
for (int next : dagGraph.adj[i]) {
inDegree[next]++;
}
}
// 진입차수가 0 인 노드 큐에 삽입
for (int i = 1; i <= dagGraph.nodeCount; ++i) {
if (inDegree[i] == 0) {
topoOrder[tail++] = i;
}
}
while (head < tail) {
int current = topoOrder[head++];
for (int next : dagGraph.adj[current]) {
inDegree[next]--;
if (inDegree[next] == 0) {
topoOrder[tail++] = next;
}
}
}
}
// DP 를 통한 최대 가중치 경로 계산
int solveMaxWeightPath() {
performTopologicalSort();
int globalMax = 0;
for (int i = 1; i <= dagGraph.nodeCount; ++i) {
int node = topoOrder[i];
dpValue[node] += dagGraph.weights[node];
globalMax = max(globalMax, dpValue[node]);
for (int next : dagGraph.adj[node]) {
dpValue[next] = max(dpValue[next], dpValue[node]);
}
}
return globalMax;
}
위 과정들을 종합하면 사이클이 포함된 유향 그래프에서도 효율적으로 최적 경로를 계산할 수 있습니다. 전체 시간 복잡도는 그래프의 노드 수 V와 간선 수 E에 대해 O(V + E)로 선형 시간에 수행 가능합니다.