백준 ATM 풀이: SCC 압축과 DAG 최장 경로

백준 ATM 문제는 사이클 안의 금액을 모두 모을 수 있다는 점 때문에 SCC 압축 후 DAG 최장 경로로 바꿔 풀 수 있습니다.

출발점에서 도달 가능한 SCC만 유효하게 보고, 레스토랑이 포함된 SCC까지의 최대 누적 금액을 계산해야 하므로 단순 BFS가 아니라 위상정렬 기반 DP가 필요합니다.

 

핵심 정리

ATM 문제의 첫 단계는 방향 그래프의 사이클을 SCC로 묶는 것입니다. SCC 내부에서는 서로 이동 가능하므로 해당 컴포넌트 안의 ATM 금액을 모두 합쳐 하나의 노드 값으로 볼 수 있습니다. 그 다음 SCC 사이의 간선으로 압축 그래프를 만들면 DAG가 되고, 출발 SCC에서 도달 가능한 컴포넌트만 대상으로 누적 금액의 최댓값을 갱신합니다. 최종 답은 레스토랑이 포함된 SCC들 중 도달 가능하면서 누적 금액이 가장 큰 값입니다.

• 사이클 안에서는 정점들을 반복해서 오갈 수 있으므로 SCC 단위로 묶습니다.
• 각 SCC의 ATM 금액은 컴포넌트 내부 정점 금액의 합입니다.
• SCC 사이의 간선을 모으면 압축 DAG를 만들 수 있습니다.
• 출발 정점이 속한 SCC에서 도달 가능한 컴포넌트만 계산 대상입니다.
• DAG 위에서는 위상정렬 순서로 DP 값을 전파할 수 있습니다.
• 레스토랑 정점도 SCC 단위로 표시해야 합니다.
• 답은 도달 가능한 레스토랑 SCC 중 최대 누적 금액입니다.
• 도달 불가능한 SCC를 섞으면 잘못된 경로가 답에 포함될 수 있습니다.

원문은 SCC 압축 이후 DAG 최장 경로 코드로 이어지므로, 문제를 SCC, 압축 그래프, 도달 가능성, DP 전파, 레스토랑 후보 선택 순서로 다시 정리했습니다. 이 순서를 놓치면 그래프는 맞게 압축해도 출발점과 무관한 컴포넌트가 계산에 섞일 수 있습니다.

이어서 볼 글

• SCC 강한 연결 요소: Kosaraju와 Tarjan 알고리즘 - 문제 풀이에서 먼저 수행하는 SCC 압축의 기본 개념이다.
• 그래프 최장거리 풀이: 트리 지름과 DAG 최장 경로 - SCC 압축 후 DAG 위에서 최장 경로 DP를 계산하는 배경이다.

 

문제링크는 여기

 

 

풀이과정

출발점은 하나로 정해져 있고, 도착점은 여러개.

현금인출은 사이클 도는게 유리하므로 SCC단위로 생각하면 됨.

도착점도 SCC단위로 묶어서 생각하면 됨.

SCC단위로 묶고나서 보면, 간선 가중치는 없는 방향그래프 이므로, 위상정렬 개념 도입해서 longest 구하면 답

(여기서 위상정렬이 아닌 단순 BFS로는 안풀린다. 그래프 최장거리 참조)

헷갈렸던 점

아래 그래프가 SCC이후에 만들어진 DAG이라고 해보자. 

1번정점이 시작, 5번 정점이 끝이라고 해보자.

위의 그래프를 아래와 같은 코드로 위상정렬하면서 돌리게 되면

enqueue({ start_v, cost[start_v] });
while (q.size()) {
    auto n = q.front(); q.pop();
    max_dist[n.v] = max(max_dist[n.v], n.w);
    for (auto adj : adj_list[n.v]) {
        max_dist[adj] = max(max_dist[adj], n.w + cost[adj]), cal[adj]=1;
        in_edge[adj]--;
        if (enqueue({ adj, max_dist[adj] })) from[adj] = n.v;
    }
}

1번노드를 처리한다음에 2번 노드처리하기전에 while()이 끝나게 된다. (2번 노드의 in_edge가 3이라서 1빼도 아직 2라서 3과 4를 처리하기 전까진 못들어가는데 3,4를 처리하지 않는 코드이다.)

하지만 정답은 1 -> 2 -> 3을 모두 계산한 최대비용이 답이었던것.. 

따라서, 아래처럼 처음에 indegree가 0인 모든 정점을 queue에 넣어주고, cal[v] 맵을 사용해서 유효한 경우에만 max_dist가 갱신되도록 해주면 OK

for (int i = base1; i < max_v + base1; i++) enqueue({ i,cost[i] });
if (start_v == -1) for (int i = base1; i < max_v + base1; i++) max_dist[i] = cost[i];
else max_dist[start_v] = cost[start_v];
vi cal(max_v + base1); cal[start_v] = 1;
while (q.size()) {
    auto n = q.front(); q.pop();
    for (auto adj : adj_list[n.v]) {
        if (cal[n.v]) max_dist[adj] = max(max_dist[adj], n.w + cost[adj]), cal[adj] = 1;
        in_edge[adj]--;
        if (enqueue({ adj, max_dist[adj] })) from[adj] = n.v;
    }
}

코드

scc_dag_kosaraju()를 라이브러리화 하고, 기존 longest()라이브러리를 활용하느라고, 범용성 관점에서 코드가 좀 길고 장황한면이 있습니다. 감안해서 봐주세요~

/*{{{*/
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include "dbg.h"  // https://github.com/sharkdp/dbg-macro
#define FileInput freopen("input.txt", "rt", stdin)
#else
#define dbg(...)
#define FileInput
#endif
//#define int long long
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define CASE_T int ___T; cin>>___T;for(int cs=1;cs<=___T;cs++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
#define endl '\n';
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(), x.end()
#define IN(n) int n;cin>>n
#define IN2(a,b) int a,b;cin>>a>>b
#define OUT(x) cout << (x) << endl
template <class T>
void OUTV(vector<T>& v) { REP(i, SZ(v)) cout << v[i] << (i + 1 == SZ(v) ? '\n' : ' '); }
typedef long long ll;
const int INF = (int)1e9;
/*}}}*/
 
struct result { vvi scc_list; vvi scc_adj_list; vi scc_cost; int scc_start_v; vi scc_end_v; };
result scc_dag_kosaraju(int max_v, int start_v, vi& end_v, vvi& adj_list, vvi& adj_rlist, vi& cost, int base1)
{
    // step1. dfs로 방문하며 말단부터 stack push
    vi visit(max_v + base1); stack<int> S;
    function<void(int n)> dfs = [&](int n) {
        if (visit[n]) return;
        visit[n] = 1;
        for (int a : adj_list[n]) dfs(a);
        S.push(n);
    };
    for (int i = base1; i < max_v + base1; i++) if (visit[i] == 0) dfs(i);
    // step2. stack에서 꺼내면서
    // 역방향으로 접근가능한 정점들을 SCC로 판정
    visit.clear(); visit.resize(max_v + base1);
    vi scc(max_v + base1);  // map. scc[v]=1 이면 v정점은 1번 SCC에 속한다고 하는것
    int scc_ix = base1;
    vvi scc_list; if (base1) scc_list.push_back(vi());
    while (S.size()) {
        int n = S.top(); S.pop();
        if (visit[n]) continue;
        vi sl;
        function<void(int n)> dfs = [&](int n) {
            if (visit[n]) return;
            visit[n] = 1;
            scc[n] = scc_ix;
            sl.push_back(n);
            for (auto a : adj_rlist[n]) dfs(a);
        };
        dfs(n);
        scc_list.push_back(sl);
        scc_ix++;
    }
    vvi scc_adj_list(scc_ix); int scc_start_v = -1; vi scc_end_v(scc_ix), scc_cost(scc_ix);
    for (int u = base1; u < max_v + base1; u++) {
        if (u == start_v) scc_start_v = scc[u];
        if (end_v[u]) scc_end_v[scc[u]] = 1;
        scc_cost[scc[u]] += cost[u];
        for (auto v : adj_list[u]) {
            if (scc[u] != scc[v]) {
                //cout << scc[u] << ' ' << scc[v] << endl;
                scc_adj_list[scc[u]].push_back(scc[v]);
            }
        }
    }
    return { scc_list, scc_adj_list, scc_cost, scc_start_v, scc_end_v };
}
struct node { int v, w; };
using vvn = vector<vector<node>>;
struct result2 { vi max_dist; int max_value; vi path; };
result2 longest(int max_v, int start_v, vvi& adj_list, vi& in_edge, vi& cost, vi& end_v, int base1) {
    vi visit(max_v + base1), max_dist(max_v + base1, -INF);
    vi from(max_v + base1, INF);
    queue<node> q;
    function<bool(node)> enqueue = [&](node n)->bool {
        if (in_edge[n.v] != 0) return false;
        q.push(n);
        return true;
    };
    for (int i = base1; i < max_v + base1; i++) enqueue({ i,cost[i] });
    if (start_v == -1) for (int i = base1; i < max_v + base1; i++) max_dist[i] = cost[i];
    else max_dist[start_v] = cost[start_v];
    vi cal(max_v + base1); cal[start_v] = 1;
    while (q.size()) {
        auto n = q.front(); q.pop();
        for (auto adj : adj_list[n.v]) {
            if (cal[n.v]) max_dist[adj] = max(max_dist[adj], n.w + cost[adj]), cal[adj] = 1;
            in_edge[adj]--;
            if (enqueue({ adj, max_dist[adj] })) from[adj] = n.v;
        }
    }
    //아래는 좀 비효율적, 위의 복잡도를 높이지 않게 하기위해 걍 놔둠
    int ra = -INF, rb = -1;
    for (int i = base1; i < max_v + base1; i++)
        if (end_v[i] && max_dist[i] > ra) ra = max_dist[i], rb = i;
    deque<int> s;
    int ix = rb;
    while (ix != INF)s.push_front(ix), ix = from[ix];
    return { max_dist, ra, vi(s.begin(), s.end()) };
}
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    FileInput;
    int V, E; cin >> V >> E;
    vvi adj_list(V + 1), adj_list2(V + 1);
    REP(i, E) {
        int a, b; cin >> a >> b;
        adj_list[a].push_back(b);
        adj_list2[b].push_back(a); // 역방향
    }
    vi cost(V + 1);
    REP1(i, V)cin >> cost[i];
    IN2(S, P);
    vi end_v(V + 1);
    REP(i, P) { IN(p); end_v[p] = 1; }
    auto r = scc_dag_kosaraju(V, S, end_v, adj_list, adj_list2, cost, true);
    int N = SZ(r.scc_adj_list) - 1;
    vi in_edge(N + 1);
    REP1(u, N) for (auto v : r.scc_adj_list[u])in_edge[v]++;
    auto r2 = longest(N, r.scc_start_v, r.scc_adj_list, in_edge, r.scc_cost, r.scc_end_v, true);
    OUT(r2.max_value);
    return 0;
}