[백준] 9370번: 미확인 도착지

📌 문제

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

📌 설명

 1부터 n까지의 노드가 존재하고, 출발 노드 s가 존재한다고 하자. 추가로 두 노드 g, h가 주어지는데, 다익스트라 알고리즘을 통해 최단 경로를 계산할 때, (g, h) 간선을 포함하는 노드를 출력해야 한다. 예를 들어 노드 k까지 최단 경로를 구했다고 하자. 이 경로에 (g, h) 간선이 포함되면 k는 답이 되며, 포함되지 않는 경우 답이 될 수 없다. 주의해야 하는 것은, 조건의 선후 관계를 헷갈리면 안 된다. 

1. 출발 노드 s로부터 각 노드까지의 최단 경로를 구한다.
2. 구한 최단 경로 중 (g, h) 간선을 포함하는 노드가 답이 된다.

위 문장은 문제를 옳게 해석한 것이다.

1. 출발 노드 s부터 각 노드까지 (g, h) 간선을 포함하도록 하는 최단 경로를 구한다.
2. 구한 최단 경로들 중 가장 최소인 최단 경로에 속하는 노드가 답이 된다.

위 문장은 문제를 잘못 해석한 것이다. 처음에 이렇게 풀었는데, 나 말고 다른 피해자도 있는 걸 보면 내가 문제는 아닌 거 같다. 문제가 조금 난해한 것 같다.

 다익스트라 알고리즘을 사용하는 것은 맞고, 그 중에서도 풀이 과정이 다양하게 나올 수 있다. 먼저 도착 노드를 d라고 할 때, s부터 (g, h) 간선까지의 최단 경로에 (g, h) 간선에서 d까지의 최단 경로를 구하는 방법이 있다. 즉, s -> g -> h -> d 경로에서 다익스트라를 각각 수행하고, s -> h -> g -> d 경로에서 다익스트라를 각각 수행하여 답이 되는 경우를 추리는 방법이다. 이 방법은 가장 직관적이나 다익스트라를 많이 수행하게 된다. 아니면 이를 조금 최적화하여 s -> g와 s -> h의 최단 경로를 구한 후, 둘 중 최소인 경우만 고려하는 방법도 있다. 예를 들어 s -> g가 s -> h보다 최단 경로라면 s -> g -> h -> d만 고려하면 된다.

 내가 시도한 방법은 우선순위 큐에 (g, h) 간선을 지났음을 표시하는 flag를 추가로 사용하는 것이었다. 그러나 WA가 나왔다. 제대로 분석한 것은 아니지만, 다익스트라에서 방문 여부를 확인하는 경우 발생하는 문제와 비슷한 맥락인 것 같다.

 제출한 정답 코드는 직관적이고 다익스트라를 한 번 사용하며, 아이디어 또한 기발하다고 생각한다. 두 가지 성질을 사용한다. 누구나 아는 성질이다.

1. 모든 자연수에 2를 곱한 수는 짝수이다.
2. 짝수에 홀수를 한 번 더하면 홀수가 된다.

 두 노드 간 가중치에 2를 곱해 배열에 저장한다. 단, (g, h) 간선의 가중치는 2배에 1을 빼서 저장한다. 즉, (g, h) 간선의 가중치는 홀수가 되며, 나머지 간선의 가중치는 짝수이다. 우리는 최단 경로의 비용이 궁금한 것이 아니다. 따라서 모든 간선의 가중치를 적절하게(다익스트라를 사용함에 있어 문제가 되지 않게) 변형해도 무방한 것이다. 이제 다익스트라를 수행한다. 만약 (g, h) 간선을 지나게 된다면 해당 도착 노드까지의 최단 경로의 비용은 홀수가 될 것이다. 이러한 방법으로 (g, h) 간선을 지났는지 여부를 판단한다.

📌 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <tuple>

#define INF 1e9

using namespace std;

int s, g, h; // 출발지, g - h 간선을 반드시 지남
vector<int> cost(2001);
vector<pair<int, int>> nodes[2001]; // nodes[x] = {y, w}: x -> y 간선의 가중치는 w

void init(int n) {
	for (int i = 0; i <= n; i++) {
		nodes[i].clear();
	}
}

void dijkstra(int n) {
	for (int i = 1; i <= n; i++) {
		cost[i] = INF;
	}
	cost[s] = 0;

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0,s });
	while (!pq.empty()) {
		int w = pq.top().first;
		int x = pq.top().second;

		pq.pop();

		if (cost[x] < w)
			continue;

		for (int i = 0; i < nodes[x].size(); i++) {
			int y = nodes[x][i].first;
			int nw = nodes[x][i].second;

			if (w + nw < cost[y]) {
				cost[y] = w + nw;
				pq.push({ cost[y],y });
			}
		}
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);

	int T;
	cin >> T;
	while (T--) {
		int n, m, t; // 교차로, 도로, 목적지 후보
		cin >> n >> m >> t;

		cin >> s >> g >> h;

		init(n);

		for (int i = 0; i < m; i++) {
			int a, b, d; // a - b 간선의 가중치는 d / 양방향
			cin >> a >> b >> d;

			// 필수 경로는 가중치를 홀수로 설정
			if ((a == g && b == h) || (a == h && b == g)) {
				nodes[a].push_back({ b,d * 2 - 1 });
				nodes[b].push_back({ a,d * 2 - 1 });
			}

			// 필수 경로가 아니라면 가중치를 짝수로 설정
			nodes[a].push_back({ b,d * 2 });
			nodes[b].push_back({ a,d * 2 });
		}

		set<int> candidate;
		for (int i = 0; i < t; i++) {
			int x;
			cin >> x;
			candidate.insert(x);
		}

		// s -> candidate[i]로 최단거리로 이동할 때, g - h 간선을 지나면 답, 그렇지 않으면 답 X
		dijkstra(n);

		for (auto dest : candidate) {
			// 만약 최소 비용이 홀수면 필수 경로를 지난 것임.
			if (cost[dest] % 2)
				cout << dest << " ";
		}
		cout << "\n";
	}
}