[백준/BOJ] 백준 10273번 : 고대 동굴 탐사

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

10273번: 고대 동굴 탐사

해당 위치에서 탐색을 하여 최대로 얻을 수 있는 이익을 cache에 저장하여 다이나믹 프로그래밍을 이용해 최대 이익을 찾고, cache에 저장된 값을 이용해서 최대 이익일 때 방문하는 동굴들을 찾아내서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits>
using namespace std;

int max_int = numeric_limits<int>::max();
int min_int = numeric_limits<int>::min();
int tc;
int n, e;
vector<int> value(20001);
vector<pair<int, int>> adj[20001]; //(비용,도착점) [시작점]
vector<int> cache(20001);
int result1;
vector<int> result2;

void Pre()
{
	for (int i = 0; i < 20001; i++)
	{
		value[i] = 0;
		adj[i].clear();
		cache[i] = max_int; //나올수 없는 값으로 초기화
	}
	value.clear();
	result2.clear();
}

//here에서 탐색하여 최대로 얻을 수 있는 이익을 반환
int Solve1(int here)
{
	int& ret = cache[here];

	if (ret != max_int)
		return ret;

	ret = value[here];

	for (int i = 0; i < adj[here].size(); i++)
	{
		int cost = adj[here][i].first;
		int there = adj[here][i].second;

		ret = max(ret, value[here] + Solve1(there) - cost);
	}

	return ret;
}

void Solve2(int here)
{
	result2.push_back(here);

	int next_there = -1;
	int next_max_value = min_int;
	for (int i = 0; i < adj[here].size(); i++)
	{
		int cost = adj[here][i].first;
		int there = adj[here][i].second;

		if (next_max_value < value[here] + cache[there] - cost)
		{
			next_max_value = value[here] + cache[there] - cost;
			next_there = there;
		}
	}

	if (next_there != -1)
		Solve2(next_there);
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> tc;

	for (int t = 0; t < tc; t++)
	{
		Pre();

		cin >> n >> e;

		for (int i = 1; i <= n; i++)
		{
			int input;
			cin >> input;

			value[i] = input;
		}

		for (int i = 0; i < e; i++)
		{
			int a, b, c;
			cin >> a >> b >> c;

			adj[a].push_back(make_pair(c, b));
		}

		result1 = Solve1(1);
		Solve2(1);

		cout << result1 << " " << result2.size() << "\n";
		for (int i = 0; i < result2.size(); i++)
			cout << result2[i] << " ";
		cout << "\n";
	}

	return 0;
}