백준 4013 - ATM(C++)

문제 링크입니다. https://www.acmicpc.net/problem/4013

4013번: ATM

SCC 알고리즘과 위상정렬 알고리즘, 약간의 DP가 섞인 문제입니다.

도시와 교차로가 주어질 때, 시작 도시에서 아무 레스토랑까지 얻을 수 있는 현금의 최대 액수를 구하는 문제입니다.

한 도시를 여러 번 도달 가능하는 점이 있기에 서로 연결되어 순환하는 도시들은 전부 현금을 가져올 수 있게 됩니다.
문제에서는 (1, 2, 4)번 도시와 같은 집합이 해당합니다.

그렇다면, ‘(1, 2, 4)번 도시는 하나로 묶어도 되지 않을까?’ 라는 생각을 가져볼 수 있습니다.
왜냐하면 한 도시를 여러번 방문할 수 있기에, 어디에서는 시작해도 3개의 도시 중 원하는 한 곳에서 나올 수 있기 때문입니다.
-> 이런 도시들의 집합을 전부 찾아서 하나의 도시로 바꾸면 문제가 한 층 쉬워질 것입니다.
-> SCC를 이용하면 하나의 도시로 바꾸는 작업을 구현할 수 있습니다.

SCC를 이용해서 각 도시의 집합을 구했다면 문제에서 주어진 그래프는 다음과 같이 나옵니다.
-> (1, 2, 4) / (3) / (5) / (6)  
문제에서 도시들간의 연결이 주어졌기 때문에 각 SCC들 간에 관계도 알 수 있게 됩니다.
예를 들어, 2번 도시에서 3번 도시로 갈 수 있으니 이는 (1, 2, 4) SCC에서 (3) SCC로 연결이 된다는 의미입니다.

‘구해진 SCC와 SCC의 관계를 통해서 어떻게 현금의 최댓값을 얻을 수 있는지?’ 를 생각해봐야합니다.
어떤 점 X에서 얻을 수 있는 최댓값을 구하려고 할 때, X번 정점까지 올 수 있는 방법들의 값들을 전부 비교해서
가장 큰 값을 찾는다면 해당 값이 최댓값이 될 것입니다.
-> SCC의 관계를 통해서 X번 정점까지 갈 수 있는 방법과 DP를 통해 탐색하면서 정점들의 최대 현금을 알 수 있습니다.

그렇다면, 이는 위상정렬을 통해서 시작 SCC에서 출발해 연결된 SCC를 찾아서
계속 해당 SCC점에서 최댓값을 갱신하면 됨을 알 수 있습니다.

하지만, 주의해야할 점이 있습니다.
문제에서 입력으로 주어진 시작점의 SCC 번호를 찾아서 해당 위치에서 시작한다면 정확한 답이 나오지 않습니다.
왜냐하면, SCC의 indgree 값은 시작점 뿐만 아니라, 모든 SCC 들의 관계를 통해서 얻어졌기 때문에
시작 위치에서만 시작한다면 해당 indgree가 정확히 감소하지 않아 위상정렬이 제대로 돌아가지 않기 때문입니다.

따라서, indgree가 0인 SCC에서 시작을 하되, 현금 비용을 갱신하는 과정은 위상 정렬을 탐색하는 과정에서
시작점이 속한 SCC를 찾았을 때부터 해주면 됩니다.


이번 문제를 정리하자면,
1. SCC를 통해 서로 순환하는 도시를 하나로 만들어준다.
2. SCC를 전부 찾았다면, 해당 SCC에서 얻을 수 있는 현금의 값, 레스토랑의 유무를 확인한다.
3. SCC간의 관계를 확인하고, 연결해줌과 동시에 indgree도 증가해준다.
4. 지금까지의 정보를 바탕으로 위상정렬과 DP를 통해 최대 현금을 구한다,



자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#define F first
#define S second

using namespace std;

int N, M;
int S, P;
vector<vector<int>> connect;
int money[500001];
int restaurant[500001];
// 입력까지 사용하는 배열
int check[500001];
vector<int> stk;
int SCC_id[500001];
int SCC_cnt, vertex;
// SCC를 찾는데 사용하는 배열
vector<vector<int>> SCC_connect;
vector<int> SCC_step;
vector<int> SCC_money;
vector<int> SCC_dp;
vector<bool> SCC_restaurant;
queue<int> q;
// 찾은 SCC를 바탕으로 SCC를 연결하고 위상정렬을 통해 답을 구하는 배열

void reset_array(){
	memset(check, -1, sizeof(check));
	memset(SCC_id, -1, sizeof(SCC_id));
}

void SCC_vector_resize(){ // 크기가 정해져 있지 않았던 vector를 구해진 SCC 갯수를 통해 정의한다.
	SCC_step.resize(SCC_cnt+1);
	SCC_money.resize(SCC_cnt+1);
	SCC_dp.resize(SCC_cnt+1);
	SCC_restaurant.resize(SCC_cnt+1);
	SCC_connect.resize(SCC_cnt+1, vector<int>());
}

int SCC(int start){ // SCC를 찾는다.
	int ret = check[start] = vertex++;
	stk.push_back(start);
	for(auto &next : connect[start]){
		if(check[next] == -1){
			ret = min(ret, SCC(next));
		}	
		else if(SCC_id[next] == -1){
			ret = min(ret, check[next]);
		}
	}
	if(ret == check[start]){
		while(1){
			int x = stk.back();
			SCC_id[x] = SCC_cnt;
			stk.pop_back();
			if(x == start) break;
		}
		SCC_cnt++;
	}
	return ret;
}

void topological_sort(){ // 구한 SCC간의 관계를 통해서 위상정렬로 답을 구한다.
	bool flag = false;
	for(int i = 0; i < SCC_cnt; i++){ 
		// 단계가 0인 SCC부터 넣는다.
		// 출발점이 속한 SCC만 넣지 않는 이유는
		// 그렇게하면 연결된 SCC의 indgree가 0이 되지 않기 때문이다.
		if(SCC_step[i] == 0) q.push(i);
	}
	SCC_dp[SCC_id[S]] = SCC_money[SCC_id[S]];
	while(!q.empty()){
		int x = q.front();
		q.pop();
		if(x == SCC_id[S]) flag = true; //출발점이 속한 SCC가 나오면 dp를 통해 값을 비교한다.
		for(auto &next : SCC_connect[x]){
			if(flag) SCC_dp[next] = max(SCC_dp[next], SCC_dp[x] + SCC_money[next]);
			SCC_step[next]--;
			if(SCC_step[next] == 0) q.push(next);
		}
	}
}

void solve(){
	reset_array();
	for(int i = 1; i <= N; i++){ // SCC를 구한다.
		if(check[i] != -1) continue;
		SCC(i);
	}
	SCC_vector_resize();
	for(int i = 1; i <= N; i++){ // 각 SCC간의 돈의 합을 구하고 레스토랑의 유무를 구한다.
		SCC_money[SCC_id[i]] += money[i];
		if(restaurant[i] == 1) SCC_restaurant[SCC_id[i]] = true;
	}
	for(int i = 1; i <= N; i++){ // 각 SCC간의 연결된 SCC와 step을 구한다.
		for(auto &next : connect[i]){ // 이전에 입력된 연결을 바탕으로 구한다.
			if(SCC_id[i] == SCC_id[next]) continue;
			SCC_connect[SCC_id[i]].push_back(SCC_id[next]);
			SCC_step[SCC_id[next]]++;
		}
	}
	topological_sort();
	int max_money = 0;
	for(int i = 0; i < SCC_cnt; i++){
		if(SCC_restaurant[i]){ // 해당 SCC에 레스토랑이 존재할 때
			max_money = max(max_money, SCC_dp[i]);
		}
	}
	cout << max_money;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	connect.resize(N+1, vector<int>());
	int x, y;
	for(int i = 1; i <= M; i++){
		scanf("%d %d", &x, &y);
		connect[x].push_back(y);
	}
	for(int i = 1; i <= N; i++){
		scanf("%d", &money[i]);
	}
	cin >> S >> P;
	for(int i = 1; i <= P; i++){
		scanf("%d", &x);
		restaurant[x] = 1;
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.