boj, 백준) 4013. ATM (C/C++)

1. 문제 링크

www.acmicpc.net/problem/4013

4013번: ATM

2. 문제 개요

모든 도로들이 일방통행으로 되어 있다. 도로들이 만나는 모든 교차로에는 ATM기가 설치되어 있다. 또, 일부 교차로에는 레스토랑이 있는데, ATM에 들릴 때마다 돈을 인출한다. 이때, 시작점에서 아무 레스토랑까지 최대한 많은 돈을 인출하여 레스토랑에 가려고 하는데, 이때 최대 얼마를 가지고 갈 수 있는지 구하는 프로그램을 작성.

 

3. 문제 힌트

문제를 보아하니.. 일단 모두 순회하여 정보를 통합해야할 것 같다. 경로를 따라간다..라고 생각하면 DFS, 하지만 여러 번 방문할 수 있고 cycle이 있기 때문에 불가능.

 

(1) Cycle을 제거할 수 없을까?

 SCC인 부분은 뽑을 수 있는 현금을 합치는 방식으로해서 그래프를 DAG로 만들어 보자,

정점을 큰 왕정점으로 만든다고 생각.

 

 

(2) 어떻게 최댓값을 구할까?

시작점을 시작으로 dp를 적용해서 최댓값을 구해보자.

나에게 올 수 있는 모든 교차로들중 최댓값을 구해야 한다.

왜냐, 업데이트를

dp[다음] = max(dp[다음], dp[현재] + 도착지의 현금)과 같은 방식으로 최댓값을 가져가면서 dp table을 만들어 나간다. dp는 부분 문제에서 항상 최댓값임을 보장해야 새 문제, 더 큰 문제에서도 그것이 최대값(최적)임을 보장한다.

 

반례

정점의 순서대로 dp table을 갱신한다고 해보자,

정점 위의 값은 ATM기가 보유한 현금이라고 해보자, 

1은 2와 4의 최댓값의 후보를 갱신할 것이고, 2는 3의 최댓값의 후보값을 갱신할 것이다.

 

자, 이제 3은 5의 값을 갱신할 것이다. (그다음 4는 6을 갱신한다.)

5는 자신과 연결된 값들을 갱신할텐데,, 실제 최댓값은 1-4-6-3-5로 오는 경로이다.

즉, 잘못된 정보, 최댓값이라는 게 보장이 되지 않은 채 DP를 적용하기 때문에.. 저 문제를 해결해야 한다.

 

자신의 이전의 모든 정점(교차로)들을 다 순회하며 DP table을 갱신할 방법은 없을까? -> 위상정렬

 

간혹 BFS로 하는 분들도 계신데, 시간이 조금 더 걸립니다. N개의 정점을 방문한다는 점은 똑같으나, 모든 연결된 간선을 확인해보고 방문했으면 방문하지 않는 그런, 추가적인 연산에서 시간이 더 소요되는 것 같습니다.

 

4. 문제 풀이

코드의 흐름을 보면,

입력 -> SCC (DAG로 만들기 위함) -> SCC로 그래프 재구성 -> 위상정렬한 순서대로 DP적용 -> 레스토랑이 존재하는 정점(SCC)들 중 최댓값을 출력

이다.

 

밑의 알고리즘을 왜 썼는지에 대한 것은 3번 문제 힌트에서 대부분 작성한 것 같습니다. 알고리즘 그 자체에 대한 설명은 다른 분들이 아주 잘 써놓으셨기 때문에..(pass)

 

SCC는 타잔 알고리즘을 사용해서 구했다.(코사라주 OK)

대부분 SCC를 구하는 것에 문제가 끝나기 때문에,,, 구한 SCC를 사용해서 새로운 그래프 만드는 것이 조금 헷갈리기도 하지만.. 잘 생각해보면서 구현해보자. 

 

그다음은 위상정렬, dp.. 이 두 부분은 단순하다. dp도 간단한 dp인편에 속하기 때문에..

하지만 3번 문제 힌트에 있듯이, 왜 위상정렬을 써야만 하는지, dp가 최댓값을 어떻게 구해 나가는지, 단순히 알고리즘만 외웠다면 이 부분을 생각해내는데 시간이 조금 오래 걸릴 수 있다.

 

문제 자체(?)가 매우 어렵다기보다는 이런 아이디어를 어떻게, 왜 써야 하는지 한 번 더 생각해볼 수 있는 재밌는 문제라고 생각한다.

 

 

5. 코드

#include <cstdio>
#include <queue>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

int n, m, start, p, cnt, ans;
vector<vector<int>> adj,scc, scc_adj;
vector<int> cash,scc_cash, restaurant, dfsn, scc_index, indegree, dp;

vector<bool> finished;
stack<int> s;
queue<int>q;

int dfs(int cur)
{
	dfsn[cur] = ++cnt;
	s.push(cur);

	int ret = dfsn[cur];

	for (int next : adj[cur]) {
		if (dfsn[next] == 0)
			ret = min(ret, dfs(next));
		else if (!finished[next])
			ret = min(ret, dfsn[next]);
	}

	if (ret == dfsn[cur]) 
	{
		vector<int> cc;
		int cur_index = scc.size();

		while (1)
		{
			int val = s.top(); s.pop();
			finished[val] = true;
			cc.push_back(val);
			scc_index[val] = cur_index;

			if (val == cur)
				break;
		}
		scc.push_back(cc);
	}
	return ret;
}

void SCC() 
{
	dfsn.resize(n + 1);
	finished.resize(n + 1);
	scc_index.resize(n + 1);
	
	for (int i = 1; i <= n; ++i)
		if (dfsn[i] == 0)
			dfs(i);

	indegree.resize(scc.size());
	scc_adj.resize(scc.size());

	//Generate a SCC graph
	for (int cur = 1; cur <= n; ++cur) 
		for (int to : adj[cur]) 
			if (scc_index[cur] != scc_index[to]) {
				scc_adj[scc_index[cur]].push_back(scc_index[to]);
				++indegree[scc_index[to]];
			}
	
	return;
}

void topology_sort()
{
	for (int i = 0; i < scc.size(); ++i) 
		if (indegree[i] == 0)
			q.push(i);
	
	//DP table initialization
	dp.resize(scc.size());
	scc_cash.resize(scc.size());

	for (int i = 1; i <= n; ++i)
		scc_cash[scc_index[i]] += cash[i];
	
	dp[scc_index[start]] = scc_cash[scc_index[start]];

	bool flag = false;

	//As SCC is DAG, it will run successfully
	while (!q.empty()) {

		int cur = q.front();
		q.pop();

		if (cur == scc_index[start])
			flag = true;

		//for dp and sorting
		for (int next : scc_adj[cur]) {

			if(flag)
				dp[next] = max(dp[next], dp[cur] + scc_cash[next]);

			--indegree[next];
			if (indegree[next] == 0)
				q.push(next);
		}
	}
	return;
}

int main()
{
	scanf("%d %d", &n, &m);

	adj.resize(n + 1);
	cash.resize(n + 1);

	for (int i = 0; i < m; ++i) {
		int from, to;
		scanf("%d %d", &from, &to);

		adj[from].push_back(to);
	}

	for (int i = 1; i <= n; ++i) 
		scanf("%d", &cash[i]);
	
	scanf("%d %d", &start, &p);
	
	restaurant.resize(p);
	
	for (int i = 0; i < p; ++i) 
		scanf("%d", &restaurant[i]);
	

	//SCC to change the graph to DAG
	SCC();

	//to decide the order of iteration
	topology_sort();


	for(int i=0; i<p; ++i)
		ans = max(ans, dp[scc_index[restaurant[i]]]);

	printf("%d", ans);

	return 0;
}

6. 결과

프로그램을 작성하면서 전역 변수를 너무 많이 쓴 것 같아 메모리가 조금 걱정이었는데 괜찮았습니다. 실제로는 이렇게 전역 변수로 막 쓰거나, 혹은 전역변수로 썼다 해도 다시 활용할 수 있는 건 다시 활용하는 방식을 사용합시다..