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

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

1504번: 특정한 최단 경로

 

 

 

 

 

 

 다익스트라 활용문제를 하나 풀어봤다. 비용이 최소가 되는 경로를 구하는 문제에 또다른 조건으로 특정 정점을 통과하는 최단 경로를 구하는 문제이다.

 

 

 

 

 

 

 

 네트워크 수업시간에 특정 노드를 방문하는 경로탐색 기법에 대해 설명을 들었던 적이 있는데 이 문제를 보고 그게 어렴풋이 생각이 났다. 그때는 개념만 들었기에 어떤식으로 구현이 될지 생각해보진 않았는데 이번에 문제를 풀면서 생각해보게 되었다.

 

 

 

 

 

 

 

 

 

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <climits>

using namespace std;

// 임의의 정점 2개를 통과해야함
// 구하고자 하는 것 : 출발지로부터 무조건 통과해야하는 정점까지의 최단 경로 + 목적지까지 최단 경로
// 주의할 것 : 임의의 정점은 2개이므로 어떤 것을 먼저 통과하는지에 따라서 최단 경로가 나뉠 수 있음


struct Vertex {
	int vertex;
	int cost;

	bool operator<(const Vertex v) const {
		return this->cost > v.cost;
	}

};

int V, E;
int firstNode, secondNode;
vector<vector<Vertex>> adjacent; // 인접 리스트 방식

void input() {
	cin >> V >> E;
	adjacent.resize(V + 1);

	for (int i = 0; i < E; i++) {
		int start, dest, cost;

		cin >> start >> dest >> cost;
		adjacent[start].push_back(Vertex{ dest, cost });

		// 방향이 없는 그래프이므로 순서를 반대로 하여 한번 더 넣어줘야 함.
		adjacent[dest].push_back(Vertex{ start, cost });
	}


	cin >> firstNode >> secondNode;
}


vector<int> dijikstra(int start) {
	priority_queue<Vertex> dijikstraQueue;
	vector<int> best; // 최단 거리
	best.resize(V + 1);
	fill(best.begin(), best.end(), INT_MAX);

	// 시작 지점 설정
	best[start] = 0;
	dijikstraQueue.push(Vertex{ start, 0 });

	while (dijikstraQueue.empty() == false) {

		Vertex curV = dijikstraQueue.top();
		dijikstraQueue.pop();

		int here = curV.vertex;

		// 최단 경로와 비교
		if (best[here] < curV.cost) continue;

		// 방문처리

		// 인접 경로를 포함하는 경로가 최단 경로인지 판단
		for (int i = 0; i < adjacent[here].size(); i++) {

			int there = adjacent[here][i].vertex;
			int nextCost = best[here] + adjacent[here][i].cost;

			if (nextCost < best[there]) { // 인접 경로를 포함하는 경우가 최단 경로라면
				// 갱신 & 큐에 방문예약 큐에 추가

				best[there] = nextCost;
				dijikstraQueue.push(Vertex{ there, nextCost });

			}
			else {
				continue;
			}
		}
	}

	return best; // 시작노드를 기준으로 최단 거리목록을 넘긴다.

}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	input();
	vector<int> startBest = dijikstra(1);
	vector<int> firstBest = dijikstra(firstNode);
	vector<int> secondBest = dijikstra(secondNode);


	int case1;
	int case2;

	if (startBest[firstNode] == INT_MAX || firstBest[secondNode] == INT_MAX || secondBest[V] == INT_MAX) {
		case1 = -1;
	}
	else {
		case1 = startBest[firstNode] + firstBest[secondNode] + secondBest[V];
	}

	if (startBest[secondNode] == INT_MAX || secondBest[firstNode] == INT_MAX || firstBest[V] == INT_MAX) {
		case2 = -1;
	}
	else {
		case2 = startBest[secondNode] + secondBest[firstNode] + firstBest[V];
	}

	if (case1 != -1 && case2 != -1) {
		cout << min(case1, case2) << endl;
	}
	else {
		cout << -1 << endl;
	}


}

 

 

 

 

 

 

 다익스트라를 사용하여 풀었다. 무조건 통과해야하는 정점을 포함하는 경로는 시작지점 -> 특정 정점 -> 목적지 순으로 각각의 최단경로를 각각 구해서 마지막에 더해주면 그것이 특정 정점을 포함하는 경로의 최단 경로가 된다. 문제에서 무조건 통과해야하는 정점은 2개라고 하였으므로 최단 경로는 어떤 정점을 먼저 통과하는지에 따라 2가지가 생성된다.

 

 

 

 

 

 

 

 

 

 목적지를 먼저간 후에 특정 정점을 통과할 수도 있지 않을까라는 생각도 해봤는데 그것은 앞서 말한 케이스안에 포함되는 것으로 결국 저 2가지 케이스만 고려하면 된다.

 

 

 

 

 

 

 

 

 

 

 그리고 문제에서 방향성이 없는 그래프라 했는데 그것을 코드에 적용을 안시켜서 한번 바로 틀렸다. 방향성이 없는 그래프라면 반대 방향으로의 데이터를 한번 더 삽입해주는 것으로 해결 가능하다.