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

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

9370번: 미확인 도착지

 

 

---

 

 

문제

---

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.

이 듀오는 대체 어디로 가고 있는 것일까?

예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하나로 가고 있고 점선으로 표시된 도로에서 냄새를 맡았다. 따라서 그들은 6으로 향하고 있다.

 

입력

---

첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다

• 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.
• 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h)
• 그 다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000)가 주어진다. a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻이다.
• 그 다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. 이 t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않다.

교차로 사이에는 도로가 많아봐야 1개이다. m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.

 

출력

---

테스트 케이스마다

• 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.

 

예제 입력

---

2
5 4 2
1 2 3
1 2 6
2 3 2
3 4 4
3 5 3
5
4
6 9 2
2 3 1
1 2 1
1 3 3
2 4 4
2 5 5
3 4 3
3 6 2
4 5 4
4 6 3
5 6 7
5
6

 

예제 출력

---

4 5
6

 

코드 

---

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

#define INF 987654321
int n, m, t;
int s, g, h;

void dijkstra(int start, vector<pair<int, int>> v[], int d[]) {
	d[start] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ d[start], start });
	while (!pq.empty()) {
		int dist = pq.top().first;
		int idx = pq.top().second;
		pq.pop();

		for (size_t i = 0; i < v[idx].size(); i++) {
			int next = v[idx][i].first;
			int cost = v[idx][i].second;
			if (d[next] > dist + cost) {
				d[next] = dist + cost;
				pq.push({ d[next], next });
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int T;
	cin >> T;
	while (T--) {
		cin >> n >> m >> t;
		cin >> s >> g >> h;

		vector<pair<int, int>> v[2001];
		int dist_s[2001];
		int dist_h[2001];
		int dist_g[2001];
		vector<int> cand;

		for (int i = 0; i < m; i++) {
			int a, b, d;
			cin >> a >> b >> d;
			v[a].push_back({ b, d });
			v[b].push_back({ a, d });
		}

		for (int i = 1; i <= n; i++) {
			dist_s[i] = INF;
			dist_h[i] = INF;
			dist_g[i] = INF;
		}

		for (int i = 0; i < t; i++) {
			int tmp;
			cin >> tmp;
			cand.push_back(tmp);
		}

		dijkstra(s, v, dist_s);
		dijkstra(h, v, dist_h);
		dijkstra(g, v, dist_g);

		sort(cand.begin(), cand.end());
		for (auto x : cand) {
			if (dist_s[x] == dist_s[h] + dist_h[g] + dist_g[x]) cout << x << ' ';
			else if (dist_s[x] == dist_s[g] + dist_g[h] + dist_h[x]) cout << x << ' ';
		}
		cout << '\n';
	}
	return 0;
}

 

2) 실패코드

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

#define INF 987654321
int n, m, t;
int s, g, h;

void dijkstra(int start, vector<pair<int, int>> v[], pair<int, bool> d[]) {
	d[start].first = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ d[start].first, start });
	while (!pq.empty()) {
		int dist = pq.top().first;
		int idx = pq.top().second;
		pq.pop();

		for (size_t i = 0; i < v[idx].size(); i++) {
			int next = v[idx][i].first;
			int cost = v[idx][i].second;
			if (d[next].first > dist + cost) {
				d[next].first = dist + cost;
				pq.push({ d[next].first, next });
				if ((idx == g && next == h) || (idx == h && next == g)) d[next].second = true;
				if (d[idx].second) d[next].second = true;
			}
		}
	}


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

	int T;
	cin >> T;
	while (T--) {
		cin >> n >> m >> t;
		cin >> s >> g >> h;

		vector<pair<int, int>> v[2001];
		pair<int, bool> dist[2001]; // first: 정점 v까지의 거리, second: 주어진 도로를 지났는지 true, false
		vector<int> cand;

		for (int i = 0; i < m; i++) {
			int a, b, d;
			cin >> a >> b >> d;
			v[a].push_back({ b, d });
			v[b].push_back({ a, d });
		}

		for (int i = 1; i <= n; i++) dist[i] = { INF, false };
		for (int i = 0; i < t; i++) {
			int tmp;
			cin >> tmp;
			cand.push_back(tmp);
		}

		dijkstra(s, v, dist);

		sort(cand.begin(), cand.end());
		for (auto x : cand) {
			if (dist[x].second) cout << x << ' ';
		}
		cout << '\n';
	}
	return 0;
}

 

 

---

 

 

처음엔 정점마다 최단경로가 냄새를 맡은 도로를 지났는지 안지났는지 true, false 값을 통해 표시해주는 방식으로 문제를 해결하려고 했다. 33%에서 계속 오류가 나고 있는데 어디서 틀렸는지 도저히 모르겠다..ㅠㅠ 나중에 다시 확인해보려고 오류코드도 같이 올림. 

 

정답 코드는 구현 내용이 간단하다.

다익스트라 함수를 하나 정의하고 각각 출발(s) 정점, g 정점, h 정점에서 출발했을 때의 거리 배열을 구한다.

경로 s -> g -> h > e(도착지) 또는 경로 s -> h -> g -> e 가 s -> e 이면( == s에서 e까지 가는 최단경로이면) e는 목적지인 것이므로 출력해준다.