[C/C++] 백준 9370번 - 미확인 도착지

✏️ 문제 링크

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

9370번: 미확인 도착지

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

다익스트라 알고리즘을 이용하는 문제입니다.

출발점으로부터 도착지 후보들까지의 최단 경로를 계산해서 이 도착지들의 최단 경로에 g와 h가 포함되어 있다면 출력하는 문제입니다. 처음에는 출발점으로부터 다익스트라를 돌리면서 경유지를 추가하였습니다. 그리고 나서 경유지를 탐색하면서 그 경유지에 g와 h가 포함된다면 그 도착점을 출력하도록 하였으나 16%에서 틀렸습니다가 계속 나왔습니다.

그래서 다른 방법으로 접근하였습니다.

출발점 -> g -> h -> 도착점 or 출발점 -> h -> g -> 도착점까지의 최단경로가 출발점 -> 도착지 후보의 최단경로와 같다면

정답으로 출력하였습니다. 나머지 세부 사항들은 아래 코드를 보시면 될 것 같습니다.

 

 

✏️ 문제 코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<memory.h>
#include<limits.h>
using namespace std;

int TC, len, node1, node2;
int n, m, t, s, g, h, a, b, d, x;
int dist_1[50001], dist_2[50001];
vector<int>result;
typedef pair<int, int>edge;
vector<edge>tree[50001];
void dijkstra(int start, int* dist);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> TC;

	while (TC--) {

		// 배열값들 모두 초기화
		result.clear();
		memset(dist_1, 0, sizeof(dist_1));
		memset(dist_2, 0, sizeof(dist_2));
		for (int i = 0; i < 50001; i++)
			tree[i].clear();

		cin >> n >> m >> t;
		cin >> s >> g >> h;

		for (int i = 0; i < m; i++) {
			cin >> a >> b >> d;
			tree[a].push_back(edge(b, d));
			tree[b].push_back(edge(a, d));
			// g에서 h까지의 경로를 미리 저장
			if (a == g && b == h || a == h && b == g)
				len = d;
		}

		// 출발점에서 돌리기
		dijkstra(s, dist_1);

		// 위에서 설명한 경로의 길이가 같은지 비교하기 위함
		if (dist_1[g] > dist_1[h]) { // 더 먼것을 node2로
			node1 = h;
			node2 = g;

		}
		else {
			node1 = g;
			node2 = h;
		}

		dijkstra(node2, dist_2); // g와 h중 start에서 더 먼 지점에서 도착점까지의 최단 경로 구하기

		for (int i = 0; i < t; i++) {
			cin >> x;
			if (dist_1[x] == dist_1[node1] + len + dist_2[x])
				result.push_back(x); // 문제 풀이에서 말했던 두 가지 경우의 수중 하나에 해당하는 경우
		}

		sort(result.begin(), result.end());
		for (int i = 0; i < result.size(); i++)
			cout << result[i] << " ";
		cout << '\n';
	}

}

void dijkstra(int start, int* dist)
{
	queue<int>q;
	for (int i = 1; i <= n; i++)
		dist[i] = INT_MAX;
	dist[start] = 0;
	q.push(start);

	while (!q.empty()) {

		int node = q.front();
		int mdist = dist[node];
		q.pop();

		for (int i = 0; i < tree[node].size(); i++) {
			int next_node = tree[node][i].first;
			int next_dist = tree[node][i].second;

			if (dist[next_node] > mdist + next_dist) {
				dist[next_node] = mdist + next_dist;
				q.push(next_node);
			}
		}
	}

}

 

 

✏️ 느낀 점

이렇게 특정 구간의 경로를 지나가는지 물어볼 때는 경유지를 탐색하기 보다는 직접 경로를 지나가게 설계해서

비교하자!

 

✏️ 비슷한 문제

https://pooreumjung.tistory.com/319

[C/C++] 백준 1504번 - 특정한 최단 경로

 

✏️ 참고

https://pooreumjung.tistory.com/299

Algorithm 공부 #16 - 그래프(다익스트라 알고리즘)