[백준/BOJ] 4013번: ATM ( SCC, 위상 정렬 응용 ) - C++ 문제 풀이

문제 설명

 

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

 

풀이

이 문제는 출발 지점으로부터 방문할 수 있는 레스토랑까지 가는 동안 구할 수 있는 금액의 최대 값을 출력하는 문제입니다.

 

이 문제를 풀기 어렵게 만드는 것은, 문제를 그래프로 변경 시, 그래프에 순환 경로가 존재한다는 것입니다.

그래서, 우선 순환 경로를 제거합니다.

그 방법은 강한 결합 요소( SCC )를 구해서, 그 요소의 정점들을 하나의 정점으로 변경하는 것입니다.

그렇게 되면, 원래의 그래프가 순환 경로가 없는 방향 그래프( DAG, Directed Acyclic Graph )가 됩니다.

 

순환 경로를 제거한 그래프 구성

 

이 과정을 코드로 작성하면 다음과 같습니다.

 

여기선, SCC를 구하기 위해 타잔( Tarjan ) 알고리즘을 사용하였습니다.

타잔 알고리즘에 관한 내용은 여기에서 볼 수 있습니다.

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

생소한 알고리즘이라면, 미리 보는 것이 나머지 코드를 보는데 도움이 될 것입니다.

 

#define SIZE    500001

vector<int> graph[SIZE];

int visited[SIZE];
int scc_num[SIZE];  // scc group

int money[SIZE];    // 정점에 있는 금액

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

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

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

    if ( loop == visited[vert]){

        int scc_money = 0;
        vector<int> scc;

        while ( !st.empty()){
            int x = st.top();
            st.pop();
            
            scc_money += money[x];	// SCC 각 정점들의 금액을 누적
            scc.push_back(x);

            if ( x == vert) 
                break;
        }

        scc_cnt++;	// SCC의 개수

        for( int x : scc){
            scc_num[x] = scc_cnt;   	// scc number 부여
            money[x] = scc_money;	// scc의 금액 총합을 저장
        }
    }
    
    return loop;
}

// main ----------------------------------------------------
stack<int> st;
int scc_cnt = 0;

for( int i = 1; i <= N; i++){   // SCC 집합 구하기

    if ( scc_num[i]) 
        continue;

    int idx = 1;
    FindSCC( st, i, idx, scc_cnt);
}

이 함수에선 SCC를 찾으면, SCC에 속한 정점의 금액을 모두 합해서, 각 SCC 정점에 저장했습니다.

아래에서, SCC를 한 정점으로 변경하면, 합해진 금액이 이 정점에 할당될 것입니다.

 

// rebuild graph
for( int i = 1; i <= N; i++){
    int sccn = scc_num[i];	// scc 번호를 사용한 그래프을 구성
    
    for( int x : graph[i]){
        int cx = scc_num[x];
        if ( cx == sccn)	
            continue;
        dag[sccn].push_back( cx );	// 정점 번호를 SCC 번호로 변경해서 그래프 구성
        indegree[cx]++;	// 위상 정렬을 위한 indegree 저장
    }

    sum_money[sccn] = cmoney[sccn] = money[i];	// SCC 금액을 기록
}

이 함수는 정점 번호를 사용하는 그래프에서, SCC 번호를 사용하는 그래프를 작성하는 함수입니다.

변수 dag가 새로 구성된 그래프이며, 이 그래프는 순환 경로가 없는 방향 그래프입니다.

 

cmoney [v]는 dag 그래프의 정점 v에 있는 금액이고,

sum_money [v]는 dag 그래프의 정점 v까지 가는 동안, 누적된 금액을 말합니다.

한 정점에 도달하는 경로가 다양하므로, 한 경로로 왔을 때의 금액을 저장했다가, 다른 경로로 왔을 때의 금액이 더 큰 경우 새로운 금액을 저장하기 위한 변수입니다.

 

이제, 새로 작성된 그래프를 위상 정렬하면서, 정점을 방문할 때마다 구할 수 있는 최대 금액을 기록합니다.

위상 정렬( Topology Sort )에 관한 내용은 여기에서 볼 수 있습니다.

[C++] 위상 정렬( Topology Sort )

// 위상 정렬
void Topology_Sort(int start, int scc_cnt){

    queue<int> q;

    for( int i = 1; i <= scc_cnt; i++){
        if ( indegree[i] == 0)  // 정렬을 시작할 정점
            q.push(i);
    }

    visited[start] = true;	// 방문한 정점 표시

    while( !q.empty()){
        int vert = q.front();
        q.pop();
    
        for( int x : dag[vert]){	// SCC 번호를 사용하는 그래프에서 탐색
            
            if (visited[vert]){
                
                // 정점이 가진 금액과, 새로운 경로를 통한 금액을 비교해서 기록
                sum_money[x] = max(sum_money[x], sum_money[vert] + cmoney[x] );
                visited[x] = true;
            }
            
            indegree[x]--;
            if ( indegree[x] == 0){
                q.push(x);
            }
        }
    }
}

// main ----------------------------------------------
int start = scc_num[S];	// scc 번호로 변환
Topology_Sort(start, scc_cnt);

위의 위상 정렬 대신 깊이 우선 탐색( DFS )나 너비 우선 탐색( BFS )을 하게 되면, 경로마다 달라지는 금액을 비교하기 위해서 방문했던 정점을 여러 번 방문하게 됩니다. 

시간제한에 걸립니다.

 

마지막으로, 레스토랑이 있는 정점에 기록되어 있는 금액 중에서 최대 금액을 출력하면 문제 해결입니다.

for( int r : restaurant){
    int sccn = scc_num[r];
    if ( visited[sccn]){	// 방문했던 정점 중에 레스토랑이 있으면
        max_money = max( max_money, sum_money[sccn]);
    }
}

printf("%d", max_money);

 

 

소스 코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
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    500001

vector<int> graph[SIZE];
vector<int> dag[SIZE];

int visited[SIZE];
int scc_num[SIZE];  // scc group

int money[SIZE];    // 정점에 있는 금액
int cmoney[SIZE];   // 변경된 그래프의 정점의 금액
int sum_money[SIZE];
int max_money = 0;

int indegree[SIZE];   // 정점의 indegree

vector<int> restaurant; // 레스토랑이 있는 교차로

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

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

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

    if ( loop == visited[vert]){

        int scc_money = 0;
        vector<int> scc;

        while ( !st.empty()){
            int x = st.top();
            st.pop();
            
            scc_money += money[x];
            scc.push_back(x);

            if ( x == vert) 
                break;
        }

        scc_cnt++;

        for( int x : scc){
            scc_num[x] = scc_cnt;   // scc number 부여
            money[x] = scc_money;
        }
    }
    
    return loop;
}

void Topology_Sort(int start, int scc_cnt){

    queue<int> q;

    for( int i = 1; i <= scc_cnt; i++){
        if ( indegree[i] == 0)  // 정렬을 시작할 정점
            q.push(i);
    }

    visited[start] = true;

    while( !q.empty()){
        int vert = q.front();
        q.pop();
    
        for( int x : dag[vert]){
            
            if (visited[vert]){
                sum_money[x] = max(sum_money[x], sum_money[vert] + cmoney[x] );
                visited[x] = true;
            }
            
            indegree[x]--;
            if ( indegree[x] == 0){
                q.push(x);
            }
        }
    }
}

int main(){

    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++){   // ATM에 들어있는 금액
        money[i] = readInt();
    }

    int S = readInt();  // start vertex
    int P = readInt();

    for( int i = 0; i < P; i++){    // 레스토랑이 있는 위치
        int vert = readInt();
        restaurant.push_back(vert);
    }

    stack<int> st;
    int scc_cnt = 0;

    for( int i = 1; i <= N; i++){   // SCC 집합 구하기

        if ( scc_num[i]) 
            continue;

        int idx = 1;
        FindSCC( st, i, idx, scc_cnt);
    }

    // rebuild graph
    for( int i = 1; i <= N; i++){
        int sccn = scc_num[i];
        
        for( int x : graph[i]){
            int cx = scc_num[x];
            if ( cx == sccn)
                continue;
            dag[sccn].push_back( cx );
            indegree[cx]++;
        }

        sum_money[sccn] = cmoney[sccn] = money[i];
    }

    fill( visited, visited+SIZE, 0);    // flag 초기화
    
    int start = scc_num[S];
    Topology_Sort(start, scc_cnt);

    for( int r : restaurant){
        int sccn = scc_num[r];
        if ( visited[sccn]){
            max_money = max( max_money, sum_money[sccn]);
        }
    }

    printf("%d", max_money);

    return 0;
}