백준 5719 - 거의 최단경로

문제

요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다.

상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다.

거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다. 

예를 들어, 도로 지도가 아래와 같을 때를 생각해보자. 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다. 시작점은 S, 도착점은 D로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경로는 두 개가 있다)거의 최단 경로는 점선으로 표시된 경로이다. 이 경로는 최단 경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 예를 들어, 아래 그림의 길이가 3인 도로의 길이가 1이라면, 거의 최단 경로는 두 개가 된다. 또, 거의 최단 경로가 없는 경우도 있다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 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. 문제해석

- 방향가중치그래프로 N개의 노드와 M개의 간선이 있다.

- S에서 D로 가려고 하는데 최단경로에 해당하는 경로들은 모두 제외한다음 다른 경로로 최단 경로에 도달하는 것이 거의 최단경로이다. 

 

1.1. 사고의 흐름

1)특정 노드에서 특정 노드까지의 최단 거리: 다익스트라, 벨만포드, 플로이드 마샬 방법들 중 생각해보아야 한다.

 

2). 노드수가 500 이하이므로 플로이드 마샬이 안될 건 없다. 가중치가 양수이므로 벨만포드를 쓸 바에는 다익스트라가 낫다.

 

3)최단 경로에 해당하는 간선은 지나지 못한다. 그렇다면 최단경로에 해당하는 간선이 무엇인지 저장을 할 방법이 필요하다.

 

4) 그리고 저장했다면, 최단경로에 해당하는 간선을 지워주는 작업이 필요하다. 

 

5)지워줬다면, 다시 나머지 경로들만을 이용해서 최단경로를 구해준다면 그게 정답일 것이다. 

 

 

 

1.2. 최단경로에 이용된 간선 찾기

이 방법에 대한 고민이 꽤나 깊었기 때문에 따로 글을 적었다.

>> https://ebang.tistory.com/68

결론적으로는 다익스트라 방법에서 직전노드를 저장해주면서 최단경로를 갱신해나가다가, 

최단경로가 만들어진 시점에서 백트레킹으로 직전노드로 이동하면서 vector에 push를 하던 어떤 작업을 하던 그 노드들을 저장하면 그것이 최단경로가 된다! 

- 암튼 그래서 다익스트라 방법을 쓸 것으로 결정!  

- 직전노드로 이동하는 건 여러 직전노드가 있을 수 있으므로 BFS를 사용한다

 

1.3. 최단경로에 해당하는 간선을 지워주기

- 간선을 지워준다는 것으로, 실제로 vector erase 함수를 쓰려고 했었다. 그러나 이 방법은 상당히 오래걸리는 문제가 있어 실제로 코딩테스트 문제를 풀 때는 사용하지 않는다는 점이 널리 알려진 사실이었다.  

- 실제로 간선을 지우지 않아도 다익스트라를 수행시 지나가지 못하는 간선임을 표시해둔다면, 문제가 쉽게 해결될 것이다. 

나같은 경우, 가중치가 0이상인 간선들이므로 음수로 설정해둔 간선이 있을 경우 지나지 못한다고 인식하도록 설정해두었다.

 

1.4. 나머지 경로들만을 이용해서 최단경로 구하기

- 가중치가 음수인(--지워진 간선)간선을 제외하고 다시한번 다익스트라를 수행하면 된다. 

 

2. 구현

 

2.1. 다익스트라 & 실제 경로 저장하기 (최단경로에 이용된 간선 찾기)

다익스트라를 수행하다보면, visited 배열을 사용하지 않는 대신 다시 방문한 노드에 대해 이용한 간선의 비용이 더 적은지 확인 후, 거리를 업데이트해주는 과정이 존재한다. 

이때, 업데이트를 해주는 간선이 바로 최단경로가 될 수 있는 후보이다. 

따라서 다음과 같이 수도 코드를 짤 수 있다. 

 

pseudo code

Alg dijkstra

1. Q.push(S)
2. while(!Q.Empty())
	u = Q.pop()
    for v in adj(u):
    	nextCost = d[u] + v.weight
        if (nextCost < d[v]) 
        	d[v] = nextCost {거리 업데이트}
            v.parent.clear()
            v.parent = u	{업데이트 될 때 선임자 저장 단, 이전에 저장된 잘못된 선임자 없애기}
            Q.push(v)
        else if(nextCost == d[v]
        	v.parent = u	{최단거리와 경로가 같을 때도 저장}

 

 

2.2. 최단경로에 이용된 간선 지우기

최단경로에 이용된 모든 간선을 지우면 된다. : 비용을 -1로 바꾼다.

Alg findroute
1. Q.push(D)
2. while(!Q.empty())
	u = Q.pop()
	for v which is u.parent
		edge = edge in (v, u):
    		edge.cost = -1
       		Q.push(u.parent)

 

2.3. 지운 간선을 제외하고 최단경로 찾기:

     2.1.의 다익스트라 알고리즘에서 u = Q.pop()뒤에 한 문장만 추가하면 된다. 

u = Q.pop()
if (u.cost < 0)
	continue

 

실제로 구현한 코드는 다음과 같다.

 

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>

int N, M, S,D;
using namespace std;
#define MAX 501
#define INF 1987654321

long long dist[MAX];
vector <vector<pair<long long, int>> > g(MAX);
vector <vector<int> > pre(MAX);
priority_queue <pair<long long, int>> PQ;
priority_queue <int> Q;


void input()
{
	long long u, v, w;
	for (int i = 0; i < M; i++)
	{
		cin >> u >> v >> w;
		g[u].push_back({ w,v });
	}
}


void dijkstra()
{
	//거리 배열 초기화
	for (int i = 0; i < N; i++)
		dist[i] = INF;
	//시작 점
	dist[S] = 0;
	PQ.push(make_pair(0, S));
	while (!PQ.empty())
	{
		long long nowcost = -PQ.top().first;
		long long now = PQ.top().second;
		PQ.pop();
		if (dist[now] < nowcost)
			continue;
		for (int i = 0; i < g[now].size(); i++)
		{
			if (g[now][i].first == -1)//갈 수 없는 길. (정상 가중치는 0이상)
				continue;
			long long nextcost = nowcost + g[now][i].first;
			int next = g[now][i].second;
			if (nextcost < dist[next])
			{
				dist[next] = nextcost;
				PQ.push({ -nextcost, next });
				pre[next].clear();
				pre[next].push_back(now);
			}
			else if (nextcost == dist[next])
				pre[next].push_back(now);
		}
	}
}

bool visited[MAX] = { 0, };

void delete_path() //벡터 순회 대신, DFS 혹은 BFS로 방문하면서 cost를 바꾸어놓쟈..!
{
	// pre에 저장된 노드들을 순서대로 방문: 사실상 역순의 방문
	//DFS로 해도 되고 BFS로 해도 될 것 같다. 
	
	Q.push(D);
	fill(visited, visited + N + 1
		, 0);
	//printf("delete path start\n");
	
	while (!Q.empty())
	{
		int now = Q.top();
		Q.pop();

		if (visited[now] == true)
			continue;

		visited[now] = true;
		for (int i = 0; i < pre[now].size(); i++)
		{
			int next = pre[now][i];			
			if (visited[next] == false)
			{
				//pre에 저장된 선임 노드를 push
				Q.push(next);

				//선임노드에서 now를 찾아서 cost를 변경한다. 
			//	printf("now - next : %d %d\n", now, next);
				for (int j = 0; j < g[next].size(); j++)
				{
					if (g[next][j].second == now)
					{
					//	printf("delete: %d -%d\n", next, now);
					//	cout << g[next][j].first <<  "\n";
						g.at(next)[j].first = -1; //선임자에서 현재로 갈 수 없는 곳이라는 의미. 
					}
				}
				

			}
		 }


	}
}

long long solve()
{
	dijkstra();
	//shortest에서갖고 있는 간선을 제거 하기
	/*
	1. dijkstra도중에 간선확인하면서 사용하지 않고 지나가기 -> 시간복잡도가 최대 *N이 되므로 지양
	2. 간선을 사용하지 못하게 만드는 알고리즘: cost를 INF로 초기화. 
	*/
	delete_path();
	dijkstra();
	if (dist[D] == INF)
		return -1;
	else
		return dist[D];
	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	while (1) 
	{
		cin >> N >> M;

		if (!N && !M)
			return 0;
		pre.clear();
		g.clear();
		g.resize(N+1);
		pre.resize(N+1);

	//	printf("check: has to be zero: pre[3].size() %d  ,%d\n", pre[3].size(), g[0].size() );
		cin >> S >> D;
		input();
		cout << solve() << "\n";


		
	}
	

}