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

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 중간에 반드시 두 정점을 거쳐서 가는 최단경로를 찾는 문제다.

 

결국 최단경로를 찾는 문제기 때문에 Dijikstra 알고리즘으로 쉽게 풀 수 있다.

 

제한사항을 보면 V의 개수가 최대 800이기 때문에 O(N^2)의 시간복잡도로 문제를 풀어도 빠르게 풀 수 있는 문제다.

 

이 문제의 특징은 양방향 간선이기 때문에 a -> b의 최단거리는 b -> a의 최단거리와 같다.

 

그러므로 이를 이용하면 최단거리를 구하기 위해서는 두 개의 값만 비교하면 된다.

 

1. 1 -> a -> b -> V로 도착하는 경우

2. 1 -> b -> a -> V로 도착하는 경우

 

위의 두 경우를 비교하면 되는데, a -> b의 최단거리와 b -> a의 최단거리가 같으므로 1- > a, b -> v의 값만 찾으면 된다.

 

그러므로 1번에서 출발해 각 정점에 도착하는 최단거리의 값들을 구하고, V번 정점에서 출발해 정점에 도착하는 최단거리의 값을 구한 다음, a->b 사이의 최단거리 값을 구했다.

(즉, Dijikstra 알고리즘으로 3개의 정점에서 시작하는 값을 알면 문제는 해결 된다.)

 

 

이후 두 값의 최소 값을 비교해 더 작은 값을 출력하면 된다.

 

 

​

[아이디어 정리]

1. Dijikstra 알고리즘으로 특정 정점에서 출발해 다른 정점에 도착하는 최단거리를 구한다.
2. 양방햔 간선이므로 a -> b, b -> a의 최단경로는 같다. 이를 이용해 3번의 계산으로 최단 거리를 구할 수 있다. 
3. 두 가지 경로의 비용을 구하고, 그 중 작은 값을 출한다. (만약 불가능한 경우 -1을 출력한다)

 

 

 

Code

 

 

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

const int INF = 10000000;
vector<int> calc(int &V, vector<vector<pair<int, int>>> &graph, int st)
{
	vector<int> visitedF(V + 1, INF);
	vector<bool> visitedTF(V + 1, false);
	visitedF[st] = 0;
	int nowNode, nowCost;
	while (true) 
	{
		nowCost = INF;
		nowNode = 0;
		for (int i = 1; i <= V; i++) 
		{
			if (!visitedTF[i]&&nowCost > visitedF[i])
			{
				nowCost = visitedF[i];
				nowNode = i;
			}
		}
		if (nowNode == 0) 
		{
			return visitedF;
		}
		visitedTF[nowNode] = true;
		for (int i = 0; i < graph[nowNode].size(); i++) 
		{
			pair<int,int> nextNode = graph[nowNode][i];
			visitedF[nextNode.first] = min(visitedF[nextNode.first], visitedF[nowNode] + nextNode.second);
		}
	}
}

int main() 
{
	int V, E;
	cin >> V >> E;
	vector<vector<pair<int, int>>> graph(V+1);
	int a, b, c;
	for (int i=0; i<E; i++)
	{
		cin >> a >> b >> c;
		graph[a].push_back(make_pair(b, c));
		graph[b].push_back(make_pair(a, c));
	}
	cin >> a >> b;
	int answer = 0;
	vector<int> stOne=calc(V,graph,1);
	vector<int> stBack = calc(V, graph, V);
	vector<int> vecAB = calc(V, graph, a);
	answer = vecAB[b];
	answer += min(stOne[a] + stBack[b], stOne[b] + stBack[a]);
	if (answer >= INF) 
	{
		cout << -1;
	}
	else 
	{
		cout << answer;
	}
	return 0;
}

 

---

Dijikstra 알고리즘에 익숙해지면 쉽게 풀 수 있는 문제다.

 

1504번: 특정한 최단 경로