[Baekjoon] 2150 – Strongly Connected Component

https://www.acmicpc.net/problem/2150

📖 문제 이해하기

강한 연결 요소란 방향 그래프에서 정점들의 최대 부분집합으로, 그 집합에 속한 임의의 두 정점 u와 v에 대해 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 의미합니다. 예를 들어, 정점 집합 {1, 2, 3}이 SCC라면 1→2→3→1과 같은 순환 경로가 가능해야 하며, 실제로는 더 복잡한 연결 구조를 가질 수 있습니다.

문제에서 주어진 예시를 보면, 그래프의 SCC들은 {a, b, e}, {c, d}, {f, g}, {h}로 구성됩니다. 특히 주목할 점은 정점 h처럼 자기 자신으로의 간선이 없어도 단일 정점이 하나의 SCC를 구성할 수 있다는 것입니다. 이는 정점에서 자기 자신으로 가는 “빈 경로”가 항상 존재하기 때문입니다.

🧠 단순한 접근법과 그 한계

가장 직관적인 접근법은 모든 정점 쌍에 대해 양방향 도달 가능성을 확인하는 것입니다. 각 정점에서 DFS나 BFS를 수행하여 다른 모든 정점으로의 도달 가능성을 확인하고, 이를 바탕으로 강한 연결 관계를 파악하는 방식입니다.

하지만 이 방법은 심각한 성능 문제를 안고 있습니다. V개의 정점이 있는 그래프에서 각 정점으로부터 O(V + E) 시간의 탐색을 수행해야 하므로, 전체 시간 복잡도가 O(V * (V + E))가 됩니다. 문제의 제약 조건인 V ≤ 10,000, E ≤ 100,000을 고려하면, 최악의 경우 약 10억 번의 연산이 필요하게 되어 시간 초과가 발생할 가능성이 높습니다. 또한 이 방법은 모든 정점 쌍의 연결성을 확인한 후 실제 SCC를 구성하는 추가적인 복잡한 과정이 필요합니다.

💡 타잔 알고리즘의 핵심 아이디어

효율적인 SCC 찾기의 핵심은 DFS 탐색 과정에서 발견되는 구조적 특성을 활용하는 것입니다. 바로 이 지점에서 타잔(Tarjan) 알고리즘의 혁신적인 아이디어가 등장합니다.

타잔 알고리즘의 핵심 통찰은 DFS 트리에서 강한 연결 요소가 형성되는 방식에 있습니다. DFS 탐색 중에 백 엣지(back edge)나 크로스 엣지를 통해 이미 방문된 정점으로 돌아갈 수 있다면, 이는 순환 구조의 존재를 의미합니다. 더 정확히 말하면, 현재 정점에서 시작하여 DFS를 진행하다가 현재 정점보다 먼저 발견된 정점으로 되돌아갈 수 있다면, 이들 사이에 강한 연결성이 존재한다는 것입니다.

알고리즘은 각 정점에 대해 두 가지 값을 관리합니다. num[v]는 정점 v가 DFS에서 발견된 순서를 나타내고, low[v]는 정점 v에서 시작하여 DFS 서브트리를 통해 도달할 수 있는 정점들 중 가장 작은 num 값을 의미합니다. 만약 어떤 정점에서 low[v] == num[v]라면, 이는 해당 정점이 하나의 SCC의 루트임을 의미합니다.

📘 타잔 알고리즘에 대하여
타잔 알고리즘은 1972년 로버트 타잔이 개발한 강한 연결 요소 찾기 알고리즘입니다. 이 알고리즘은 단일 DFS 탐색으로 모든 SCC를 찾아내는 것이 특징이며, 스택을 사용하여 현재 탐색 중인 경로를 추적합니다. DFS의 백트래킹 과정에서 SCC를 식별하는 방식으로 O(V + E) 시간 복잡도를 달성합니다.

논문: https://arxiv.org/abs/2201.07197

스택의 역할도 매우 중요합니다. DFS 탐색 과정에서 방문한 정점들을 스택에 저장하고, SCC의 루트를 발견했을 때 해당 루트까지의 모든 정점들을 스택에서 제거하여 하나의 SCC를 구성합니다. 이 과정에서 스택의 LIFO 특성이 DFS의 탐색 순서와 완벽하게 일치하여 올바른 SCC 구성을 보장합니다.

🔍 알고리즘 동작 과정 상세 분석

구체적인 예시를 통해 알고리즘의 동작을 살펴보겠습니다. 정점 6개(1~6)로 구성된 그래프에서 간선이 1→2, 2→3, 3→1, 3→4, 4→5, 5→6, 6→4와 같이 주어진 경우를 생각해봅시다.

DFS를 정점 1부터 시작합니다. 먼저 정점 1을 방문하여 num[1] = low[1] = 1로 설정하고 스택에 추가합니다. 정점 1에서 정점 2로 이동하여 num[2] = low[2] = 2로 설정합니다. 계속해서 정점 3으로 이동하면 num[3] = low[3] = 3이 됩니다.

정점 3에서는 두 개의 인접 정점이 있습니다. 먼저 정점 1로 가는 간선을 확인하는데, 정점 1은 이미 방문되었고 현재 스택에 있으므로 low[3] = min(low[3], num[1]) = min(3, 1) = 1로 업데이트됩니다. 이는 정점 3에서 시작하여 정점 1까지 도달할 수 있음을 의미합니다.

다음으로 정점 4를 방문하여 num[4] = low[4] = 4로 설정합니다. 정점 4에서 정점 5로, 정점 5에서 정점 6으로 계속 진행합니다. 정점 6에서 정점 4로 돌아가는 간선을 발견하면, low[6] = low[5] = low[4] = 4로 업데이트됩니다.

백트래킹 과정에서 low[v] == num[v]인 정점을 발견하면 SCC를 구성합니다. 정점 4에서 이 조건이 만족되므로, 스택에서 정점 4까지의 모든 정점들(6, 5, 4)을 제거하여 하나의 SCC {4, 5, 6}을 구성합니다. 마찬가지로 정점 1에서도 이 조건이 만족되어 SCC {1, 2, 3}을 구성합니다.

💻 소스 코드

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

vector<vector<int>> ans;              <em>// 최종 SCC들을 저장할 2차원 벡터</em>
unordered_map<int, vector<int>> G;    <em>// 그래프를 인접 리스트로 표현</em>
int low[10001], num[10001], vis[10001]; <em>// low값, 발견순서, 방문상태 배열</em>
int counter = 0;                      <em>// DFS 발견 순서를 위한 전역 카운터</em>
vector<int> st;                       <em>// DFS 경로를 추적하는 스택</em>

void getSCC(int node) {
    <em>// 현재 노드의 발견순서와 low값을 동일하게 초기화</em>
    low[node] = num[node] = ++counter;
    vis[node] = 1;                    <em>// 방문 표시 (현재 DFS 경로에 있음을 의미)</em>
    st.push_back(node);               <em>// 스택에 현재 노드 추가</em>
    
    <em>// 현재 노드의 모든 인접 노드를 탐색</em>
    for (auto & x : G[node]) {
        if (vis[x] == -1) {           <em>// 아직 방문하지 않은 노드인 경우</em>
            getSCC(x);                <em>// 재귀적으로 DFS 수행</em>
        }
        if (vis[x] == 1) {            <em>// 현재 DFS 경로에 있는 노드인 경우 (백엣지 발견)</em>
            <em>// 현재 노드의 low값을 인접 노드의 low값과 비교하여 갱신</em>
            low[node] = min(low[node], low[x]);
        }
    }
    
    <em>// 현재 노드가 SCC의 루트인지 확인 (low값과 발견순서가 같으면 루트)</em>
    if (low[node] == num[node]) {
        vector<int> temp;             <em>// 새로운 SCC를 저장할 임시 벡터</em>
        
        <em>// 스택에서 현재 노드까지 모든 노드를 pop하여 SCC 구성</em>
        while(!st.empty()) {
            int curr = st.back();     <em>// 스택의 top 원소 가져오기</em>
            st.pop_back();            <em>// 스택에서 제거</em>
            temp.push_back(curr);     <em>// 현재 SCC에 추가</em>
            vis[curr] = 0;            <em>// 방문 상태를 완료로 변경</em>
            if (curr == node) break;  <em>// SCC의 루트에 도달하면 중단</em>
        }
        
        <em>// SCC 내 노드들을 오름차순으로 정렬 (문제 요구사항)</em>
        sort(temp.begin(), temp.end());
        ans.push_back(temp);          <em>// 전체 결과에 현재 SCC 추가</em>
    }
}

int main()
{
    ios::sync_with_stdio(false);      <em>// 입출력 속도 최적화</em>
    cin.tie(nullptr);
    
    int V, E, u, v;
    cin >> V >> E;                    <em>// 정점 수와 간선 수 입력</em>
    
    <em>// 모든 간선 정보를 읽어서 그래프 구성</em>
    for (int i = 0; i < E; ++i) {
        cin >> u >> v;
        G[u].push_back(v);            <em>// u에서 v로 가는 방향 간선 추가</em>
    }
    
    <em>// 배열 초기화: 모든 노드를 미방문 상태로 설정</em>
    memset(low, -1, sizeof(low));
    memset(num, 0, sizeof(num));
    memset(vis, -1, sizeof(vis));     <em>// -1: 미방문, 1: 현재경로, 0: 완료</em>
    
    <em>// 모든 정점에 대해 DFS 수행 (연결되지 않은 컴포넌트 처리)</em>
    for (int i = 1; i <= V; ++i) {
        if (vis[i] == -1) {           <em>// 아직 방문하지 않은 정점이면</em>
            getSCC(i);                <em>// 해당 정점부터 SCC 탐색 시작</em>
        }
    }
    
    cout << ans.size() << "\n";       <em>// 찾은 SCC의 총 개수 출력</em>
    
    <em>// SCC들을 가장 작은 원소 기준으로 정렬 (문제 요구사항)</em>
    sort(ans.begin(), ans.end());
    
    <em>// 각 SCC의 모든 원소와 구분자 -1 출력</em>
    for (auto &arr : ans) {
        for (auto &x : arr) {
            cout << x << " ";
        }
        cout << -1 << "\n";           <em>// 각 SCC의 끝을 나타내는 -1 출력</em>
    }
    
    return 0;
}

🔁 코사라주 알고리즘과의 비교

SCC를 찾는 다른 대표적인 알고리즘으로는 코사라주(Kosaraju) 알고리즘이 있습니다. 코사라주 알고리즘은 원본 그래프에서 DFS를 수행하여 완료 시간 순서를 기록한 후, 그래프의 간선 방향을 모두 뒤집은 전치 그래프에서 완료 시간의 역순으로 DFS를 다시 수행하는 방식입니다.

두 알고리즘 모두 O(V + E) 시간 복잡도를 가지지만, 타잔 알고리즘은 단일 DFS 패스로 모든 SCC를 찾을 수 있어 실제 구현에서 더 효율적입니다. 또한 추가적인 그래프 변환이나 여러 번의 DFS가 필요하지 않아 메모리 사용량도 상대적으로 적습니다. 반면 코사라주 알고리즘은 개념적으로 더 직관적이어서 이해하기 쉽다는 장점이 있습니다.

📌 핵심 포인트와 활용

타잔 알고리즘의 핵심은 DFS 탐색 과정에서 발견되는 백엣지 정보를 활용하여 강한 연결성을 판단하는 것입니다. low 값의 전파 과정을 통해 각 정점이 도달할 수 있는 가장 이른 조상을 추적하고, 이를 바탕으로 SCC의 경계를 정확히 식별합니다.

이 문제에서 우리가 얻은 중요한 통찰은 복잡한 그래프 구조 문제도 DFS의 체계적인 탐색 과정과 적절한 자료구조의 조합으로 효율적으로 해결할 수 있다는 것입니다. 특히 스택을 활용한 경로 추적과 백엣지를 통한 순환 구조 감지는 다양한 그래프 알고리즘에서 응용할 수 있는 핵심 기법입니다.