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

1. 참고

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

9370번: 미확인 도착지

 

2. 접근 방법 & 문제 풀이

문제의 입&출력을 이해하는 데에도 시간이 걸리는 문제이므로 정독하길 바란다.

간단하게 이 문제에 대해서 설명하자면,

기본적으로 정점과 간선을 가지는 양방향 그래프이며

s라는 출발점에서 시작하여 (g, h)라는 링크를 꼭 지나는 최단 거리를 찾는 문제이다.

 

처음 이 문제를 보았을 때 머릿 속에는 다익스트라 알고리즘이 생각났다.

그도 그럴 것이, '최단거리' 하면 '다익스트라 알고리즘' 하는 패턴은 나에게 익숙했기 때문이다.

또한 음수 가중치에 대한 내용이 없었으므로 첫 접근은 당연히 '다익스트라' 였다.

 

나는 이 문제를 '우선순위큐를 이용한 다익스트라 알고리즘'으로 접근하되,

최단 거리를 저장하는 dist 벡터에 (g, h) 방문 여부를 bool 형태로 저장하는 식으로 계산하였다.

 

3. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>

#define INF 21470000

using namespace std;

typedef pair<int, int> P;

vector<pair<int, bool>> Dijkstra(vector<vector<P>> &graph, int start, int g, int h)
{
	priority_queue<P, vector<P>, greater<P>> pq;
	vector<pair<int, bool>> dist(graph.size(), make_pair(INF, false));
	dist[start].first = 0;
	dist[start].second = false;

	pq.push(make_pair(0, start));

	int curNode;
	bool curPass;

	while (!pq.empty())
	{
		curNode = pq.top().second;
		pq.pop();
		
		for (int i = 0; i < graph[curNode].size(); i++)
		{
			int via = graph[curNode][i].first + dist[curNode].first;
			int there = graph[curNode][i].second;

			if (dist[there].first > via || (dist[there].first == via && dist[there].second == false)) {
				if (dist[curNode].second == true || (curNode == g && there == h) || (curNode == h && there == g))
				{
					dist[there].first = via;
					dist[there].second = true;
					pq.push(make_pair(via, there));
				}
				else
				{
					dist[there].first = via;
					dist[there].second = false;
					pq.push(make_pair(via, there));
				}
			}
		}
	}

	return dist;
}

int main(void)
{
	int T;
	cin >> T;
	
	for (int c = 0; c < T; c++)
	{
		vector<vector<P>> graph;

		int n, m, t;

		cin >> n >> m >> t;
		graph.assign(n, vector<P>());

		int s, g, h;
		cin >> s >> g >> h;

		while (m--)
		{
			int a, b, d;
			cin >> a >> b >> d;

			graph[a - 1].push_back(make_pair(d, b - 1));
			graph[b - 1].push_back(make_pair(d, a - 1));
		}

		vector<int> cands;
		for (int i = 0; i < t; i++)
		{
			int cand;
			cin >> cand;
			cands.push_back(cand - 1);
		}

		vector<pair<int, bool>> result = Dijkstra(graph, s - 1, g - 1, h - 1);
		vector<int> answers;

		for (int i = 0; i < cands.size(); i++)
		{
			if (result[cands[i]].second == true)
			{
				answers.push_back(cands[i]);
			}
		}

		sort(answers.begin(), answers.end());

		for (int i = 0; i < answers.size(); i++)
		{
			if (i != 0) cout << " ";
			cout << answers[i] + 1;
		}

		if(answers.size() != 0) cout << '\n';
	}

	return 0;
}

 

4. 어려웠던 점

이 문제를 풀 때 가장 어려웠던 점은

 

if (dist[there].first > via || (dist[there].first == via && dist[there].second == false))

 

위의 지점이었다. 다익스트라 알고리즘은 단순히

'새로운 경로가 기존의 경로보다 짧은 경로라면 갱신한다.' 이다.

하지만 이렇게 하면 경로의 길이가 같을 때 (g, h)를 지나는 최신 경로와 기존 경로의 길이가 같을 때

제대로 갱신되지 않는 경우가 생긴다. 이러한 경우는 다음과 같은 경우이다.