백준 11779 c++ -[PlusUltraCode]

[필자 사고]

전형적인 다익스트라 알고리즘을 사용하여 푸는 문제이다.

 

이 문제의 특이한 점은 최단거리의 지나간 경로를 저장해야 된다는 점이다.

 

지나간 경로를 저장하는 방법은 크게 2가지가 있다.

 

트리형태로 배열을 만들어 부모노드와 자식노드를 연결하는 방법과

 

백트래킹을 이용하여 역추적 하는 방법이 있다.

 

필자는 백트래킹을 이용하여 문제를 해결했다.

 

백트래킹을 잠깐 설명하겠다.

 

1. 시작지점에서 다익스트라 알고리즘을 적용하면 최단 거리가 만들어진다.

 

2. 원래 저장해놨던 그래프 방향을 반대로 해놓은 상태를 새로운 배열에 저장한다.

 

3. 끝 지점부터 현재값-비용=다음값 과 같은 형태를 찾으면 된다. 

 

[소스코드]

 

 

 

 

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

typedef pair<int, int> Node;

vector<vector<pair<int,int>>> Arr;
vector<bool> visited;
vector<long> pathLoad;
vector<int> path;
vector<vector<Node>> RArr;
int N, M;
int Start, End;
bool check = false;

void Dijkstra(int S,int E) {
	priority_queue<Node, vector<Node>,greater<Node>> pq;
	pq.push({ 0,S });
	pathLoad[S] = 0;
	while (!pq.empty()) {
		int nowIdx = pq.top().second;
		pq.pop();
		if (visited[nowIdx] == true)continue;
		visited[nowIdx] = true;
		for (Node nextNode : Arr[nowIdx]) {
			int nextIdx = nextNode.second;
			int nextCost = nextNode.first;
			if (pathLoad[nextIdx] > pathLoad[nowIdx] + nextCost) {
				pathLoad[nextIdx] = pathLoad[nowIdx] + nextCost;
				pq.push({ pathLoad[nextIdx], nextIdx });
			}
		}
	}
}

void Input() {
	cin >> N >> M;
	Arr.resize(N + 1);
	visited.resize(N + 1, false);
	pathLoad.resize(N + 1, LONG_MAX);
	RArr.resize(N + 1);
	for (int i = 0; i < M; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		Arr[s].push_back({ w,e });
		RArr[e].push_back({ w,s });
	}
	cin >> Start >> End;
	

}

void DFS(int nowIdx) {

	if (nowIdx == Start) {
		check = true;
		return;
	}

	visited[nowIdx] = true;
	for (Node nextNode : RArr[nowIdx]) {
		int nextIdx = nextNode.second;
		int nextCost = nextNode.first;
		if (visited[nextIdx]==false
			&&pathLoad[nowIdx] - nextCost == pathLoad[nextIdx]) {
			
			path.push_back(nextIdx);
			DFS(nextIdx);
			if (check == true)return;
		}
	}
}

void Solve() {
	Dijkstra(Start, End);
	visited.clear();
	visited.resize(N + 1, false);
	path.push_back(End);
	DFS(End);
	cout << pathLoad[End] << '\n';
	cout << path.size()<<"\n";
	for (int i = path.size() - 1; i >= 0; i--) {
		cout << path[i] << " ";
	}
}



int main(void) {
	Input();
	
	Solve();
}