개요

백준 5719: 거의 최단 경로

• 입력
  입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있다. 둘째 줄에는 시작점 S와 도착점 D가 주어진다. (S ≠ D; 0 ≤ S, D < N) 다음 M개 줄에는 도로의 정보 U, V, P가 주어진다. (U ≠ V ; 0 ≤ U, V < N; 1 ≤ P ≤ 103) 이 뜻은 U에서 V로 가는 도로의 길이가 P라는 뜻이다. U에서 V로 가는 도로는 최대 한 개이다. 또, U에서 V로 가는 도로와 V에서 U로 가는 도로는 다른 도로이다.

  입력의 마지막 줄에는 0이 두 개 주어진다.

• 출력
  각 테스트 케이스에 대해서, 거의 최단 경로의 길이를 출력한다. 만약, 거의 최단 경로가 없는 경우에는 -1을 출력한다.

접근방식

1. 대충 문제를 보자마자 다익스트라를 사용하여 최단거리가 갱신되는 과정에서 해당 지점까지 갈때 방문한 노드 배열을 가지고 어떻게 하겠구나라고 생각은 들었지만, 감이 안잡혔다.

2. 다른사람의 풀이를 보니 딱 깨달았다. 최단거리를 구한후 최단거리에 해당하는 간선을 모두 지우고 다시 다익스트라를 사용하는 방식이다!

3. 하지만 다익스트라를 통해 최단거리의 루트정보를 담는 배열을 저장한다 해도, 이 배열에는 하나의 루트정보만 들어있지 최단거리의 모든 루트가 저장이 안 되어있어서 고민이였다.
   다익스트라를 돌리고 최단거리의 루트를 제거하고 다시 다익스트라를 돌리고, 지금 루트가 최단거리인지 또 파악하고 맞다면 또 제거하고,
   이런 방식으로 하나하나 다 지우면 너무 비효율적일 것 같아서 다시 검색했다.

4. 기본적으로 간선의 정보를 담는 구조체를 선언한다.

   struct Edge{
   	int U;
   	int V;
   	int dist;
   	bool isShortest;
   };

   U는 출발점 , V는 도착점, dist는 간선의 길이, isShortest는 해당간선이 최단거리루트인지 체크하는 변수다.
   

5. 그 후, 간선 전체 정보를 저장하는 v벡터와
   시작지점에서 시작하는 순방향 정보들을 저장하는 su 벡터,
   도착지점에서 시작하는 역방향 정보들을 저장하는 pre벡터가 필요하다.

   vector<Edge> v;
   vector<vector<int>> pre;
   vector<vector<int>> su;

   for (int i = 0; i < M; i++) {
   	cin >> tmp1 >> tmp2 >> dist;
   	v.push_back({ tmp1,tmp2,dist,false });
   	su[tmp1].push_back(i);
   	pre[tmp2].push_back(i);
   }

   v의 인덱스값을 저장하므로 su는 tmp1과 연결된 간선 전체 정보를 v에서 꺼내쓴다.

6. 다익스트라를 한번 진행하여 최단거리값을 저장한다.

7. 그 후, 도착지점에서 pre벡터를 이용해 최단거리를 구한다.
   최단거리인지 판단하는 방식은 시작점에서
   curNode까지의 최단거리= preNode까지의 최단거리+ preNode와 curNode사이 거리
   가 성립하면 preNode에서 curNode까지의 간선이 최단거리에 해당하는 간선이다.
   queue를 하나 선언해서 bfs방식으로 각 간선을 판단한다.

   void DeleteShortestPath() {
   	//시작지점D를 큐에 푸시
   	queueForFindingShortestPath.push(D);
   	fill(visited, visited + 500, false);
   	//BFS시작
   	while (!queueForFindingShortestPath.empty()) {
   		int curNode = 0;
   		do {
   			curNode = queueForFindingShortestPath.front();
   			queueForFindingShortestPath.pop();
   		} while (!queueForFindingShortestPath.empty() && visited[curNode]);
   
   		//큐가 비었는데 curNode가 방문한 노드라면 break;
   		if (visited[curNode]) break;
   		visited[curNode] = true;
   
   		for (int elem: pre[curNode]) {
   			int preNode = v[elem].U, preDist = v[elem].dist;
   			//만약 curNode까지의 최단거리가 preNode를 거친 루트라면 해당 루트까지의 최단거리가 맞다.
   			if (minDist[curNode] == minDist[preNode] + preDist) {
   				queueForFindingShortestPath.push(preNode);
   				//최단거리 경로라고 체크해줌으로써 다음 다익스트라에서 이 간선무시함
   				v[elem].isShortest = true;
   			}
   		}
   	}
   }

8. 이제 최단 거리에 해당하는 모든 간선의 isShortest는 true로 체크 되어있으므로 isShortest가 true라면 패스하는 식으로 다익스트라 알고리즘을 실행하면 된다.

   void Deijkstra() {
   	fill(minDist, minDist + 500, INF);
   	fill(visited, visited + 500, false);
   	minDist[S] = 0;
   	pq.push({ minDist[S],S });
   
   	while (!pq.empty()) {
   		int curNode = 0;
   		do {
   			curNode = pq.top().second;
   			pq.pop();
   		} while (!pq.empty() && visited[curNode]);
   
   		if (visited[curNode]) {
   			break;
   		}
   		visited[curNode] = true;
   		//curNode와 연결된 간선들의 정보는 v[p]에 들어있음
   		for (int p : su[curNode]) {
   			//curNode에서 p로가는 루트가 최단거리 루트라면 진행하지않고 continue
   			if (v[p].isShortest) continue;
   			
   			int nextNode = v[p].V, nextDist = v[p].dist;
   			if (minDist[nextNode] > minDist[curNode] + nextDist) {
   				minDist[nextNode] = minDist[curNode] + nextDist;
   				pq.push({minDist[nextNode],nextNode});
   			}
   		}
   	}
   }

전체 코드

#include<iostream>
#include<vector>
#include<queue>

using namespace std;
int N, M, S, D;
struct Edge{
	int U;
	int V;
	int dist;
	bool isShortest;
};
//간선 벡터
vector<Edge> v;
//도착점으로 부터 역방향 벡터
vector<vector<int>> pre;
//시작지점으로부터 순방향 벡터
vector<vector<int>> su;
queue<int> queueForFindingShortestPath;
int minDist[501];
bool visited[501];
int INF = 1'000'000'000;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>>pq;

void Deijkstra();
void DeleteShortestPath();

void Input() {
	int tmp1, tmp2,dist;
	while (1) {
		cin >> N >> M;
		if (N == 0 && M == 0) return;
	

		cin >> S >> D;
		v.clear();
		pre.clear();
		pre.resize(N);
		su.clear();
		su.resize(N);
		while (!queueForFindingShortestPath.empty()) queueForFindingShortestPath.pop();
		
		for (int i = 0; i < M; i++) {
			cin >> tmp1 >> tmp2 >> dist;
			//v에 간선정보 저장
			v.push_back({ tmp1,tmp2,dist,false });
			//v의 인덱스값을 저장하므로 su는 tmp1과 연결된 간선 전체 정보를 v에서 꺼내쓴다.
			su[tmp1].push_back(i);
			//마찬가지로 pre는 인덱스 i로 tmp2와 연결된 간선 전체 정보를 저장함
			pre[tmp2].push_back(i);

		}
		Deijkstra();
		if (minDist[D]==INF) {
			cout << -1 << '\n';
			continue;
		}
		DeleteShortestPath();
		Deijkstra();
		if (minDist[D] == INF) {
			cout << -1 << '\n';
			continue;
		}
		cout << minDist[D]<<'\n';
	}
}

void Deijkstra() {
	fill(minDist, minDist + 500, INF);
	fill(visited, visited + 500, false);
	minDist[S] = 0;
	pq.push({ minDist[S],S });

	while (!pq.empty()) {
		int curNode = 0;
		do {
			curNode = pq.top().second;
			pq.pop();
		} while (!pq.empty() && visited[curNode]);

		if (visited[curNode]) {
			break;
		}
		visited[curNode] = true;
		//curNode와 연결된 간선들의 정보는 v[p]에 들어있음
		for (int p : su[curNode]) {
			//curNode에서 p로가는 루트가 최단거리 루트라면 진행하지않고 continue
			if (v[p].isShortest) continue;
			
			int nextNode = v[p].V, nextDist = v[p].dist;
			if (minDist[nextNode] > minDist[curNode] + nextDist) {
				minDist[nextNode] = minDist[curNode] + nextDist;
				pq.push({minDist[nextNode],nextNode});
			}
		}
	}
}

void DeleteShortestPath() {
	//시작지점D를 큐에 푸시
	queueForFindingShortestPath.push(D);
	fill(visited, visited + 500, false);
	//BFS시작
	while (!queueForFindingShortestPath.empty()) {
		int curNode = 0;
		do {
			curNode = queueForFindingShortestPath.front();
			queueForFindingShortestPath.pop();
		} while (!queueForFindingShortestPath.empty() && visited[curNode]);

		//큐가 비었는데 curNode가 방문한 노드라면 break;
		if (visited[curNode]) break;
		visited[curNode] = true;

		for (int elem: pre[curNode]) {
			int preNode = v[elem].U, preDist = v[elem].dist;
			//만약 curNode까지의 최단거리가 preNode를 거친 루트라면 해당 루트까지의 최단거리가 맞다.
			if (minDist[curNode] == minDist[preNode] + preDist) {
				queueForFindingShortestPath.push(preNode);
				//최단거리 경로라고 체크해줌으로써 다음 다익스트라에서 이 간선무시함
				v[elem].isShortest = true;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
}

문풀후생

도착점에서 역방향 간선 정보 벡터를 가지고 BFS를 통해
모든 최단 경로를 찾아가는 방식이 굉장히 놀라웠던 문제다.