[BOJ] 백준 4013. ATM (Platinum II)

예전에 AC받았다가, 데이터가 추가되면서 WA로 바뀐 문제를

오늘 한번 다시 도전해봤다.

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

4013번: ATM

난이도가 상당함에도, Solve수가 상당히 많은 문제.

kks227님의 블로그에서 SCC 예제문제이기도 하고, 애초에 scc + topology 연습문제로 좋은 문제이기 때문에 많이 풀린 것이 아닐까 예상된다.

 

오랜만에 scc를 풀어본 것이라 간단하게 해설을 써보겠다.

---

의식의 흐름 및 해설

단방향 그래프이고, 최대한 많은 현금 액수를 레스토랑에 챙겨가야 하는 문제이다.

사이클일 경우, 그 사이클에 속하는 교차로의 현금을 모두 챙길 수 있다. 따라서, 그래프 내에 SCC들을 모두 체크해준다.

SCC는 같은 SCC 내의 노드들끼리는 모두 탐색할 수 있다는 의미이며, 이는 사이클이라는 의미이기도 하다. (서로 동치라는 의미는 아니다.)

또한, SCC는 하나의 노드 자체도 가능하기 때문에, 그래프는 SCC들로 이루어져 있음을 확인할 수 있다. 따라서 문제는 서로 다른 scc를 탐색하면서 가장 많은 현금을 얻는 문제로 바뀌게 된다.

 

따라서 각 scc를 numbering 해주며, 

출발점이 속한 scc를 출발점으로 설정해준다.

 

단방향 그래프이기 때문에 순서가 정해져있으므로 위상정렬을 돌려야 한다.

이 때, indegree가 0인 scc가 출발점scc 외에 다른 scc들이 있을 수 있으므로 출발점에서 도달 가능한 scc인지 체크해주는 can[MAX] 배열을 만들어주자. 이걸 만들어주지 않으면 예제에선 문제가 없겠지만, 아래 경우에서 문제가 생긴다.

빨간색 SCC는 탐색불가능

빨간색 SCC는 출발점에서 도달할 수 없는 SCC임에도 불구하고,

can[MAX] 배열이 없을 경우 빨간색 SCC에서 수많은 현금을 챙겨 답이 더 뻥튀기되는 현상을 놓칠 수 있다.

---

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
const int MAX = 500001;
const int INF = 0x3f3f3f3f;
int N, M, d[MAX], id, sccNum[MAX], w[MAX], S, cnt;
int in[MAX], sccW[MAX], sccMaxW[MAX];
vector<int> v[MAX], c[MAX];
vector<vector<int>> SCC;
bool finished[MAX], restaurant[MAX], sccRes[MAX], can[MAX];
stack<int> s;
int dfs(int x) {
	d[x] = id++;
	s.push(x);

	int parent = d[x];
	for (auto i : v[x]) {
		if (d[i] == -1)
			parent = min(parent, dfs(i));
		else if (!finished[i])
			parent = min(parent, d[i]);
	}
	if (parent == d[x]) {
		vector<int> scc;
		while (1) {
			int t = s.top();
			s.pop();
			scc.push_back(t);
			finished[t] = true;
			sccNum[t] = SCC.size();
			if (t == x)
				break;
		}
		SCC.push_back(scc);
	}
	return parent;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		v[a].push_back(b);
	}
	fill(d, d + N, -1);
	for (int i = 0; i < N; i++) {
		if (d[i] == -1)
			dfs(i);
	}
	for (int i = 0; i < N; i++) {
		cin >> w[i];
	}
	cin >> S >> cnt;
	S--;
	S = sccNum[S];
	for (int i = 0; i < cnt; i++) {
		int n;
		cin >> n;
		restaurant[--n] = true;
	}
	for (int i = 0; i < N; i++) {
		sccW[sccNum[i]] += w[i];
		if (restaurant[i])
			sccRes[sccNum[i]] = true;
		for (auto j : v[i]) {
			if (sccNum[j] != sccNum[i]) {
				c[sccNum[i]].push_back(sccNum[j]);
				in[sccNum[j]]++;
			}
		}
	}
	queue<int> q;
	for (int i = 0; i < SCC.size(); i++) {
		sccMaxW[i] = sccW[i];
		if (!in[i])
			q.push(i);
	}
	can[S] = true;
	int ans = 0;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (auto i : c[cur]) {
			if (can[cur]) {
				sccMaxW[i] = max(sccMaxW[i], sccMaxW[cur] + sccW[i]);
				can[i] = true;
			}
			if (--in[i]==0) {
				q.push(i);
			}
		}
	}
	for (int i = 0; i < SCC.size(); i++) {
		if (can[i] && sccRes[i])
			ans = max(ans, sccMaxW[i]);
	}
	cout << ans << "\n";
}

---

플레티넘2에 갈만한 문제라 본다.

구현량이 어마어마하다..