Algorithm in A..Z - 백준 4013 ATM

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

4013번: ATM

---

접근

1. SCC를 만들고 각 Component를 새로운 하나의 노드로 생각하고 Component의 구성 요소로 SCC Component간 연결할 수 있는 간선을 구하여 새로운 Graph를 구한다.

 

2. DP를 사용하여 최대로 인출할 수 있는 금액을 구한다.

---

코드

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

constexpr int NOT_VISITED = -1;

class SCC {
private:
    int n = 0;
    stack<int> st;
    vector<int> isVisited;

    int dfs(int index) {
        st.push(index);
        isVisited[index] = n++;

        int number = isVisited[index];
        for (auto &next : map[index]) {
            if (isVisited[next] == NOT_VISITED) {
                number = min(number, dfs(next));
            } else if (sccNumber[next] == NOT_VISITED) {
                number = min(number, isVisited[next]);
            }
        }

        if (number == isVisited[index]) {
            vector<int> cycle;
            while (!st.empty()) {
                int component = st.top(); st.pop();

                cycle.push_back(component);
                sccNumber[component] = (int)scc.size();
                if (component == index) {
                    break;
                }
            }

            scc.push_back(cycle);
        }

        return number;
    }
public:
    vector<int> sccNumber;
    vector<vector<int>> map, scc;

    explicit SCC(vector<vector<int>> &map, int initIndex = 0) : map(map) {
        isVisited = vector<int>(map.size(), NOT_VISITED);
        sccNumber = vector<int>(map.size(), NOT_VISITED);

        for (int index = initIndex; index < map.size(); ++index) {
            if (isVisited[index] == NOT_VISITED) {
                dfs(index);
            }
        }
    }

    void debugSCC() {
        cout << "scc" << "\n";
        for (int i = 0;i < scc.size();++i) {
            cout << i << " : ";
            for (auto &value : scc[i]) {
                cout << value << " ";
            }
            cout << "\n";
        }

        cout << endl;
    }

    void debugSCCNumber() {
        cout << "sccNumber" << "\n";
        for (auto &value : sccNumber) {
            cout << value << " ";
        }

        cout << endl;
    }

    void debug() {
        cout << "SCC Class" << "\n";
        debugSCC();
        debugSCCNumber();
        cout << endl;
    }
};

class Solve {
private:
    vector<int> weight, dp;
    vector<bool> isFinished;
    vector<vector<int>> map;

public:
    explicit Solve(SCC &scc, vector<int> &atm, vector<bool> &isRestaurant) {
        map = vector<vector<int>>(scc.scc.size());
        for (int i = 0;i < scc.scc.size();++i) {
            for (auto &component : scc.scc[i]) {
                for (auto &e : scc.map[component]) {
                    int next = scc.sccNumber[e];
                    if (i != next) {
                        map[i].push_back(next);
                    }
                }
            }
        }

        weight = vector<int>(scc.scc.size());
        for (int i = 0;i < scc.scc.size();++i) {
            for (auto &component : scc.scc[i]) {
                weight[i] += atm[component];
            }
        }

        isFinished = vector<bool>(scc.scc.size());
        for (int i = 0;i < scc.scc.size();++i) {
            for (auto &component : scc.scc[i]) {
                if (isRestaurant[component]) {
                    isFinished[i] = true;
                    break;
                }
            }
        }

        dp = vector<int>(scc.scc.size(), NOT_VISITED);
    }

    int dfs(int index) {
        if (dp[index] != NOT_VISITED) {
            return dp[index];
        }

        int result = 0;
        for (auto &next : map[index]) {
            result = max(result, dfs(next));
        }

        if (result == 0) {
            if (isFinished[index]) {
                dp[index] = weight[index];
            } else {
                dp[index] = 0;
            }
        } else {
            dp[index] = weight[index] + result;
        }

        return dp[index];
    }

    void debugMap() {
        cout << "map" << "\n";
        for (int i = 0;i < map.size();++i) {
            cout << i << " : ";
            for (auto &value : map[i]) {
                cout << value << " ";
            }
            cout << "\n";
        }

        cout << endl;
    }

    void debugWeight() {
        cout << "weight" << "\n";
        for (auto &value : weight) {
            cout << value << " ";
        }

        cout << endl;
    }

    void debugIsFinished() {
        cout << "isFinished" << "\n";
        for (auto value : isFinished) {
            cout << value << " ";
        }

        cout << endl;
    }

    void debug() {
        cout << "Solve Class" << "\n";
        debugMap();
        debugWeight();
        debugIsFinished();

        cout << endl;
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> map(n + 1);
    while (m--) {
        int s, e;
        cin >> s >> e;

        map[s].push_back(e);
    }

    vector<int> atm(n + 1);
    for (int i = 1;i <= n;++i) {
        int value;
        cin >> value;

        atm[i] = value;
    }

    int s, k;
    cin >> s >> k;

    vector<bool> isRestaurant(n + 1);
    while (k--) {
        int i;
        cin >> i;

        isRestaurant[i] = true;
    }

    SCC scc = SCC(map, 1);
    Solve solve = Solve(scc, atm, isRestaurant);

    cout << solve.dfs(scc.sccNumber[s]) << "\n";
//
//    scc.debug();
//    solve.debug();
}