[백준/BOJ] 4196번: 도미노 ( 코사라주 Kosaraju 알고리즘 응용 ) - C++ 문제 풀이

문제 설명

 

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

 

풀이

이 문제는 최소 몇 번을 손대야 모든 도미노를 쓰러뜨릴 수 있는지를 출력하는 문제입니다.

 

이 문제를 처음 맞닥뜨렸을 때, 가장 먼저 떠오르는 것은 깊이 우선 탐색이나, 너비 우선 탐색일 수 있습니다.

예를 들어, 깊이 우선 탐색으로 방문이 가능한 정점들을 한 부분집합으로 만들면, 이 집합은 손짓 한 번으로 모두 쓰러뜨릴 수 있습니다.

이렇게 해서, 부분 집합의 개수를 구하면 되는 문제 같습니다.

 

그러나, 다음 예제를 보면 조금 다른 과정이 필요한 것을 알 수 있습니다.

 

이 그래프는 1번 정점부터 깊이 우선 탐색을 하면, { 1, 2, 3 }과 { 4 } 탐색 이렇게 두 번의 탐색 과정이 필요합니다.

그러나, 4번 정점부터 탐색을 시작하면, 한 번이면 충분합니다.

 

어떻게, 4번 정점부터 탐색을 시작할 수 있을까요?

 

이때 사용할 수 있는 알고리즘이 코사라주( Kosaraju ) 알고리즘입니다.

코사라주 알고리즘은 주어진 방향 그래프에서 강한 연결 요소( SCC )를 구하는 알고리즘입니다.

 

하지만, 이 문제는 SCC를 구하는 문제는 아닙니다.

그럼에도, 이 알고리즘을 참조하려는 이유는, 이 알고리즘의  SCC를 구하는 과정이 문제를 푸는데 도움이 되기 때문입니다.

코사라주 알고리즘은 여기에 정리해 두었습니다.

[C++] 코사라주( Kosaraju ) 알고리즘 ( Strongly Connected Component, SCC 구하기 )

 

코사라주 알고리즘은 정점들을 탐색하는데 stack을 사용합니다.

두 번의 정점을 깊이 우선 탐색( DFS )을 하는데, 첫 번째 탐색 시에 stack에 정점을 넣고,

두 번째 탐색 시에 stack에 들어있는 정점 순으로 탐색을 합니다.

 

이렇게 되면, 첫 번째 탐색 종료 시,

indegree가 0인 정점이 있다면 그 정점이 stack의 top에 위치하게 됩니다.

위의 이미지의 그래프에서 4번 정점이 indegree가 0인 정점입니다.

 

그리고, 두 번째 탐색 시, stack 정점 순으로 탐색을 하므로,

4번 정점이 먼저 탐색되어, 모든 정점을 한 번에 방문할 수 있습니다.

 

따라서, 위의 그래프 도미노는 한 번으로 모두 쓰러뜨릴 수 있습니다.

 

이러한 과정을 코딩으로 작성하면 다음과 같습니다.

#define SIZE    100000

vector<int> graph[SIZE+1];
bool visited[SIZE+1];

// 1차 탐색
void DFS1( int vert, stack<int>& st){

    visited[vert] = true;
    
    for( int x : graph[vert]){
        
        if ( !visited[x] ){
            DFS1( x, st);
        }
    }

    st.push(vert);	// vert에 연결된 정점들이 먼저 탐색된 후에 stack에 저장
}

// 2차 탐색
void DFS2( int vert){

    visited[vert] = true;
    
    for( int x : graph[vert]){	// 역방향 그래프가 아니라, 원래 그래프에서 다시 탐색
        
        if ( !visited[x] ){
            DFS2( x);
        }
    }
}

위 함수 DFS2가 코사라주 알고리즘의 함수와 다른 점은,  SCC를 찾고자 하는 탐색이 아니기 때문에 역방향 그래프를 탐색할 필요가 없다는 것입니다.

 

위의 함수들을 사용하는 main함수는 다음과 같습니다.

코사라주 알고리즘을 사용하는 것과 같습니다.

int main(){

    int nShowCase = readInt();

    stack<int> st;

    for( int k = 0; k < nShowCase; k++){

        int N = readInt();
        int M = readInt();
        int a, b;
        for( int i = 0; i < M; i++){
            a = readInt();
            b = readInt();

            graph[a].push_back(b);	// 그래프 구성
        }

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

            if ( !visited[i]){
                DFS1(i, st);    // 원래 그래프 탐색
            }
        }

        fill( visited, visited+SIZE, false);    // visited 배열 초기화

        int cnt = 0;
        while( !st.empty()){
            int vert = st.top();    // 스택에 저장된 순서대로 탐색
            st.pop();

            if ( !visited[vert]){
                DFS2(vert);   
                cnt++;
            }
        }

        printf("%d\n", cnt);

        // clear previous data
        for( int i = 1; i <= N; i++){
            graph[i].clear();
        }
        fill( visited, visited+SIZE, false);    // visited 배열 초기화
    }

    return 0;
}

 

 

소스코드

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

// 입출력 소스 --------------------------------------------
#define WBUF_SIZE (1 << 20)

char rbuf[WBUF_SIZE];
int ridx, nidx;

inline char read() {
    if (ridx == nidx) {
        nidx = fread(rbuf, 1, 1 << 20, stdin);
        if (!nidx) return 0;
        ridx = 0;
    }
    return rbuf[ridx++];
}
inline int readInt() {
    int sum = 0;
    char now = read();
    bool flg = false;

    while (now <= 32) now = read();
    if (now == '-') flg = true, now = read();
    while (now >= 48) sum = sum * 10 + now - '0', now = read();

    return flg ? -sum : sum;
}
//----------------------------------------------------------

#define SIZE    100000

vector<int> graph[SIZE+1];
bool visited[SIZE+1];

void DFS1( int vert, stack<int>& st){

    visited[vert] = true;
    
    for( int x : graph[vert]){
        
        if ( !visited[x] ){
            DFS1( x, st);
        }
    }

    st.push(vert);
}

void DFS2( int vert){

    visited[vert] = true;
    
    for( int x : graph[vert]){
        
        if ( !visited[x] ){
            DFS2( x);
        }
    }
}

int main(){

    int nShowCase = readInt();

    stack<int> st;

    for( int k = 0; k < nShowCase; k++){

        int N = readInt();
        int M = readInt();
        int a, b;
        for( int i = 0; i < M; i++){
            a = readInt();
            b = readInt();

            graph[a].push_back(b);
        }

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

            if ( !visited[i]){
                DFS1(i, st);    // 원래 그래프 탐색
            }
        }

        fill( visited, visited+SIZE, false);    // visited 배열 초기화

        int cnt = 0;
        while( !st.empty()){
            int vert = st.top();    // 스택에 저장된 순서대로 탐색
            st.pop();

            if ( !visited[vert]){
                DFS2(vert);   
                cnt++;
            }
        }

        printf("%d\n", cnt);

        // clear previous data
        for( int i = 1; i <= N; i++){
            graph[i].clear();
        }
        fill( visited, visited+SIZE, false);    // visited 배열 초기화
    }

    return 0;
}