[BOJ] 백준 22358. 스키장 (Gold II)

UCPC 2021 예선에 나온 문제이다.

본 대회 당시, 다익스트라+dp로 뇌절쳤던 문제여서 다시 풀어보았다.

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

22358번: 스키장

AC받은 풀이를 먼저 살펴보고,

다익스트라가 안되는 이유를 포스팅하겠다.

---

AC 풀이

N이 최대 10만이지만, 리프트 횟수가 최대 10이다.

또한, longest path algorithm이지만, ai<bi이므로 DAG를 형성한다.

따라서 사이클이 존재하지 않으며, 

또한 현재 위치와, 남은 리프트 횟수가 같을 경우 메모이제이션이 가능하므로 dp[N][K]로 table을 만들 수 있다.

 

주의할 점은, ti<=10^9이므로 long long으로 해야 WA를 받지 않는다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pl;
const int MAX = 100001;
const ll LNF = 1e16;
ll N, M, K, S, T, d[MAX][11], ans = -1;
vector<pl> v[MAX];
ll dp(ll cur, ll cnt) {
	if (cnt > K)
		return -LNF;
	if (cnt == K && cur == T)
		return 0;
	ll& ret = d[cur][cnt];
	if (ret != -1)
		return ret;
	ret = -LNF;
	for (auto i : v[cur]) {
		if (cnt < K && i.second < cur)
			ret = max(ret, dp(i.second, cnt + 1));
		else if (i.second > cur)
			ret = max(ret, dp(i.second, cnt) + i.first);
	}
	return ret;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> M >> K >> S >> T;
	while (M--) {
		ll a, b, cost;
		cin >> a >> b >> cost;
		v[a].push_back({ cost, b });
		v[b].push_back({ cost, a });
	}
	memset(d, -1, sizeof(d));
	ll ans = dp(S, 0);
	if (ans < 0)
		cout << -1 << "\n";
	else
		cout << dp(S, 0) << "\n";
}

---

dijkstra 풀이가 TLE인 이유?

dijkstra의 cmp를 바꾸면 최장거리로 가능하지 않을까 싶어 아래 문제의 KCM Travel과 같이 접근해보려 했으나, 큰 실수였다.

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

10217번: KCM Travel

음수 간선이 존재하거나, 최장거리를 구하는 문제일 경우, dijkstra는 가능하다는 보장이 없다.

 

이 문제는 음수 간선은 따로 존재하지 않는다.

역방향으로 가는 간선이 존재하긴 하지만, 이것은 리프트 횟수로 따로 적절히 처리해주면 음수 간선이라 보기는 어렵다.

 

다만, 이 문제는 최장거리를 구하는 문제이기 때문에 TLE가 날 수 밖에 없다.

 

dijkstra는 최단거리를 구하기 위해 priority_queue를 사용한다.

더 최단거리인 길이 있다면 그것으로 갱신하여 다항시간 내에 최단거리를 찾기 때문이다.

그러나, 최장거리를 구하는 문제로 바뀐다면 NP-Hard로 바뀌게 된다.

왜냐하면, 최장거리 알고리즘을 dijkstra로 접근한다면, 어떤 길 A가 가장 긴 거리라 하자. 

최장거리를 구하기 위해 우선순위큐는 최대힙으로 설정했을 것이므로, 이 A에서 앞으로 계속 나아가 끝까지 길을 탐색할 것이다. 그런데, 알고보니 A보다 더 긴 거리의 길 B가 있었다면, B로 갱신한 후에 B에서 앞으로 계속 나아가 끝까지 길을 탐색해야 될 것이다.

이러한 과정이 계속 반복되면 결국 지수시간복잡도를 가지게 된다. 따라서 최장거리일 경우 NP-Hard이다.

 

자세한 내용은 아래 질문글에서 확인할 수 있다.

https://www.acmicpc.net/board/view/72425

글 읽기 - 아래 코드의 시간복잡도가 궁금합니다.

 

NP-Hard이지만 삽질이 가능한 다른 문제는 아래 포스팅에서 구경할 수 있다.

https://kth990303.tistory.com/69

[BOJ] 백준 20927. Degree Bounded Minimum Spanning Tree (Gold I)

---

문제에서 배운 게 꽤나 많다.

최장거리, 음수 간선이 존재할 경우 dijkstra를 남발하지 않도록 주의하자.