[백준/BOJ] 2150번: Strongly Connected Component ( SCC 타잔 알고리즘 ) - C++ 문제 풀이

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/2150

 

풀이

이 문제는 방향 그래프가 주어졌을 때, 그 안에 존재하는 강한 연결 요소( Strongly Connected Component, SCC )를 구해 출력하는 문제입니다.

 

강한 연결 요소는 방향 그래프에서 임의의 두 정점을 선택하더라도, 두 정점 간에 경로가 존재하는 최대 부분 집합을 말합니다.

 

이러한 강한 연결 요소를 구하는 알고리즘이 두 가지 있는데,

하나는 코사라주( Kosaraju ) 알고리즘이고, 다른 하나는 타잔( Tarjan ) 알고리즘입니다.

 

이 문제에서는 타잔 알고리즘을 사용해서 문제를 풀었습니다.

강한 연결 요소와 타잔 알고리즘에 관한 내용은 여기에 정리해 두었습니다.

[C++] 타잔( Tarjan ) 알고리즘 ( Strongly Connected Component, SCC 구하기 )

 

이 알고리즘을 따라 코드를 작성하면 다음과 같습니다.

#define SIZE    10000

vector<int> graph[SIZE+1];	// 문제에서 주어진 방향 그래프
vector< vector<int> > scc_arr;	// SCC를 담는 버퍼
int visited[SIZE+1];
bool finished[SIZE+1];  // 이미 한 SCC에 속해있음을 표시

int DFS( int vert, int& idx, stack<int>& st){	// 타잔 알고리즘

    visited[vert] = idx++;	// 탐색 번호
    st.push(vert);

    int loop = visited[vert];	// 현재 탐색 번호
    for( int x : graph[vert]){
        if ( !visited[x] ){
            loop = min( loop, DFS( x, idx, st));	// 연결된 정점 탐색
        }
        else if ( !finished[x]){	// 순환 경로가 있으면 작은 탐색 번호로 교체
            loop = min( loop, visited[x]);
        }
    }

    if ( loop == visited[vert]){	// 탐색이 시작되는 정점인 경우 SCC 구성

        vector<int> scc;
        while ( !st.empty()){
            int x = st.top();
            st.pop();

            scc.push_back(x);
            finished[x] = true;	// SCC를 구성하는 정점이 다시 탐색되지 않도록 표시
            if ( x == vert) 
                break;
        }

        sort( scc.begin(), scc.end());
        
        // 지역 변수의 불필요한 복사를 방지하지 위해서 이동 문법 사용
        scc_arr.push_back( move(scc) );	
    }
    
    return loop;
}

위 코드 대부분은 타잔 알고리즘의 글에서 설명한 코드와 동일합니다.

 

나머지는 문제의 요구 사항을 충족시키기 위해,

구해진 SCC 벡터를 오름차순으로 정렬하고, 그 결과를 전역 버퍼에 저장하는 부분만 좀 다릅니다.

 

여기서는, 구해진 지역 변수 scc를 전역 버퍼에 담는 과정에서 불필요한 복사가 일어나지 않도록,

이동 문법(  move semantics )을 사용했습니다.

std::move 함수를 사용하면, 복사 생성자를 호출하는 대신, 이동 생성자를 호출하기 때문에, 지역 변수의 데이터를 복사해서 저장하는 불필요한 과정을 생략할 수 있습니다.

 

move 함수에 관한 내용은 여기서 볼 수 있습니다.

[C++] 우측값 참조( rvalue reference )와 이동 생성자( move constructor )

 

 

소스코드

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

#define SIZE    10000

vector<int> graph[SIZE+1];
vector< vector<int> > scc_arr;
int visited[SIZE+1];
bool finished[SIZE+1];  // computed already

int DFS( int vert, int& idx, stack<int>& st){

    visited[vert] = idx++;
    st.push(vert);

    int loop = visited[vert];
    for( int x : graph[vert]){
        if ( !visited[x] ){
            loop = min( loop, DFS( x, idx, st));
        }
        else if ( !finished[x]){
            loop = min( loop, visited[x]);
        }
    }

    if ( loop == visited[vert]){

        vector<int> scc;
        while ( !st.empty()){
            int x = st.top();
            st.pop();

            scc.push_back(x);
            finished[x] = true;
            if ( x == vert) 
                break;
        }

        sort( scc.begin(), scc.end());
        scc_arr.push_back( move(scc) );
    }
    
    return loop;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
        
    int V, E;
    cin >> V >> E;

    int a, b;
    for( int i = 0; i < E; i++){	// 방향 그래프 구성
    
        cin >> a >> b;

        graph[a].push_back(b);
    }

    stack<int> st;

    for( int i = 1; i <= V; i++){

        if ( finished[i]) 
            continue;

        int idx = 1;
        DFS( i, idx, st);
    }

    int scc_cnt = scc_arr.size();
    sort( scc_arr.begin(), scc_arr.end());	// scc들을 오름차순으로 정렬

    // print result
    cout << scc_cnt << endl;

    for( int i = 0; i < scc_cnt; i++){
        for( int x : scc_arr[i]){
            cout << x << " ";
        }
        cout << -1 << endl;
    }

    return 0;
}