[C++] 4013번 ATM - DP, 그래프 이론, 위상 정렬, 강한 연결 요소

1. 문제

• 반디치는 레스토랑에 가기 전 ATM 기기에 있는 현금 전부를 인출하려고 한다. 반디치는 각 ATM 기기에 현금이 얼마나 들어 있는지 알고 있다. 동일한 도로나 교차로를 여러 번 지날 수 있고, ATM 기기의 현금은 새로 보충되지 않는다. 모든 교차로에는 각각 1개씩 ATM기가 존재하며 레스토랑은 여러 교차로 위에 있고 그중 어느 곳으로 가도 상관없다. 반디치가 출발 장소에서 어떤 레스토랑까지 이동하면서 인출할 수 있는 현금의 최대 액수가 얼마인지를 계산하는 프로그램을 작성하시오.

<입력>

• - 1 -   교차로 수, 도로의 수를 나타내는 2개의 정수 $N,M(1\le N,M\le 500,000)$
  • 교차로는 1~N까지 번호로 표시된다.
• - M개의 줄 -   각 도로의 시작 교차로 번호와 끝 교차로 번호를 나타내는 2개의 정수가 주어진다.
• - M+2 -   두 개의 정수 S, P가 주어진다. S는 출발 장소, P는 레스토랑의 개수이다. $P(1\le P\le N)$
• - M+3 -   각 레스토랑이 있는 교차로의 번호를 나열한 P개의 정수
• 각 ATM 기기에 들어 있는 현금의 액수는 0 이상 4,000 이하이다. 모든 입력에서 경로의 출발 장소로부터 일방 통행 도로를 통해 도달 가능한 레스토랑이 항상 하나 이상 존재한다.

<출력>

• 반디치가 출발 장소에서 어떤 레스토랑까지 이동하면서 인출할 수 있는 현금의 최대 액수를 출력하시오.

2. 재정의

• 각 노드마다 가중치가 있고 단방향 그래프가 주어졌을 때 시작 노드와, 특정 여러 노드가 종점 노드가 될 수 있다. 같은 노드와, 간선을 여러 번 지날 수 있을 때 얻을 수 있는 가중치의 최댓값을 구하시오.

3. 해결 방법

• SCC로 단위체로 묶는다. (단위별로 묶음으로서 계산 수를 줄일 수 있음.)
• SCC에서 더 이상 영향을 주지 않는(위상 정렬로 시작 위치로 부터 갈 수 없는 정점을 모두 제거(degree = INF)한다.) 노드를 제거하고 위상 정렬을 수행한 후 DP를 계산한다.

4. 실수한 점, 개선할 점

• 시작 노드에서 출발해서 갈 수 없는 곳을 제거해야 하고 이는 위상 정렬로 수행할 수 있다.
• 단순 BFS로 DP를 수행하면 계산 순서가 잘못 될 수 있으므로 반드시 위상 정렬을 수행한 후 이를 기준으로 DP를 계산하여야 한다.
• DP값은 int 범위를 넘어갈 수 있다.

 

<코드>

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>

using namespace std;
typedef long long ll;

const int INF = 987654321;
const int MAX_N = 500001;

// <문제>
// 교차로의 수 N, 도로의 수 M
int N, M;
// 방향 그래프
vector<int> adj[MAX_N];
// 출발 장소 S, 레스토랑의 개수 P
int S, P;
// 레스토랑이 있는 교차로
bool restaurant[MAX_N];
// ATM기기가 보유한 현금의 액수
ll Cost[MAX_N];

// SCC Tarjan Algorithm
stack<int> st;
int discover[MAX_N], scc[MAX_N];
int sccCnt, sccSize;

// DP
vector<int> sccadj[MAX_N];
ll sccCost[MAX_N];
ll dp[MAX_N];
ll maxCash;
bool sccRestaurant[MAX_N];

// topology Sort
int degree[MAX_N];
queue<int> q;
vector<int> topologyResult;

// SCC Tarjan Algorithm
int dfs(int no) {
    st.push(no);
    discover[no] = sccCnt++;
    int parent = discover[no];
    
    for(auto next : adj[no]) {
        if(discover[next] == -1)
            parent = min(parent, dfs(next));
        else if(scc[next] == -1)
            parent = min(parent, discover[next]);
    }
    
    if(parent == discover[no]) {
        while(true) {
            int here = st.top();
            st.pop();
            scc[here] = sccSize;

            if(restaurant[here])
                sccRestaurant[sccSize] = true;
            sccCost[sccSize] += Cost[here];
            
            if(here == no)
                break;
        }
        sccSize++;
    }
    
    return parent;
}

// 위상 정렬
void topologySort(int st) {
    q.push(st);
    
    // 진입 못하는 곳 제거하기
    queue<int> tq;
    for(int i=1; i<=sccSize; i++)
        if(!degree[i] && i != st) {
            degree[i] = INF;
            tq.push(i);
        }
    
    // (못가는 곳 = (진입차수 = 0))인 곳은 제거하기
    for(int i=1; i<=sccSize; i++) {
        if(tq.empty())
            break;
        
        int here = tq.front();
        tq.pop();
        
        for(auto next : sccadj[here]) {
            if(next != st && !(--degree[next])) {
                tq.push(next);
                degree[next] = INF;
            }
        }
    }
    
    for(int i=1; i<=sccSize; i++) {
        // 큐가 비었을 경우(못가는 곳이 존재했던 경우) break
        if(q.empty())
            break;
        
        int here = q.front();
        q.pop();
        
        for(auto next : sccadj[here]) {
            if(!(--degree[next])) {
                q.push(next);
                topologyResult.push_back(next);
            }
        }
    }
}

void bfs() {
    for(auto here : topologyResult)
        for(auto next : sccadj[here])
            dp[next] = max(dp[next], dp[here] + sccCost[next]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    // <초기화>
    memset(discover, -1, sizeof discover);
    memset(scc, -1, sizeof scc);
    sccSize = sccCnt = 1;
    
    // <input>
    cin >> N >> M;
    for(int i=0; i<M; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
    }
    for(int i=1; i<=N; i++) {
        int x;
        cin >> x;
        Cost[i] = x;
    }
    cin >> S >> P;
    for(int i=0; i<P; i++) {
        int x;
        cin >> x;
        restaurant[x] = true;
    }
    
    // Tarjan SCC Algorithm
    for(int i=1; i<=N; i++) {
        if(discover[i] == -1)
            dfs(i);
    }
    
    for(int i=1; i<=N; i++)
        for(auto next : adj[i])
            if(scc[i] != scc[next])
                sccadj[scc[i]].push_back(scc[next]);
                // 위상 정렬용 진입 차수 증가
    
    sccSize--;
    // 그룹 공통 원소 제거
    for(int i=1; i<=sccSize; i++)
        sccadj[i].erase(unique(sccadj[i].begin(), sccadj[i].end()), sccadj[i].end());
    // topology Sort용 진입차수 설정하기
    for(int i=1; i<=sccSize; i++)
        for(auto next : sccadj[i])
            degree[next]++;
    
    int st = scc[S];
    
    topologyResult.push_back(st);
    topologySort(st);
    
    for(int i=1; i<=sccSize; i++)
        dp[i] = sccCost[i];
    bfs();
    
    for(auto x : topologyResult)
        if(sccRestaurant[x])
            maxCash = max(maxCash, dp[x]);
    
    cout << maxCash;
    
    return 0;
}

 

<문제 바로가기>

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

4013번: ATM

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.