백준 5719 : 거의 최단 경로

www.acmicpc.net/problem/5719

5719번: 거의 최단 경로

이 문제는 최단 경로에 포함되는 간선을 이용하지 않고 이동하였을 때 목적지까지의 최단 경로를 구하는 문제이다.

 

다음과 같은 로직으로 문제를 해결하였다.

 

1. 모든 간선을 사용할 수 있는 상태에서 다익스트라 알고리즘으로 최단 경로를 찾는다. 이 때 최단 경로 까지 오는 데 지나 온 모든 길을 저장한다.

2. 지나온 길을 되돌아가면서 길을 삭제한다.

3. 다시 다익스트라 알고리즘을 사용하여 최단 경로를 찾는다.

 

지나온 길을 되돌아가면서 삭제할 때 입력받아둔 간선을 찾아서 지워야하는데 벡터 자료구조를 사용 시 해당 노드에서 해당 간선을 찾는데 최악의 경우 O(n)의 시간이 걸리므로 이를 방지하기 위하여 O(1)의 시간복잡도로 원하는 간선에 접근할 수 있는 unordered_map 자료구조를 사용하였다. 

코드로 구현하면 아래와 같다.

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <unordered_map>

#define INF 1e9

using namespace std;

int N, M, s, d;
int dist[500];
vector<int> path[500];
unordered_map<int, int> cost[500];

int dijkstra() {
	int cur_pos, cur_dist, next_pos, next_dist;
	unordered_map<int, int>::iterator iter;
	priority_queue<pair<int, int>> pq;
	
    	//다익스트라 알고리즘을 사용하여 최단 경로를 구하고 경로를 저장한다.
    	pq.emplace(0, s);
	dist[s] = 0;
	while (!pq.empty()) {
		cur_dist = -pq.top().first;
		cur_pos = pq.top().second;
		pq.pop();

		if (dist[cur_pos] < cur_dist) continue;
		for (iter = cost[cur_pos].begin(); iter != cost[cur_pos].end(); ++iter) {
			next_pos = iter->first;
			next_dist = cur_dist + iter->second;
			if (dist[next_pos] > next_dist) {
				if (path[next_pos].size() != 0) {
					path[next_pos].clear();
				}
                		//path에는 해당 노드로 오기 직전 노드 번호를 저장
				path[next_pos].emplace_back(cur_pos);
				dist[next_pos] = next_dist;
				pq.emplace(-next_dist, next_pos);
			}
            		//동일한 dist값으로 도달한 값도 저장해준다.
            		//최단 경로가 하나가 아닐수도 있기 때문.
			else if (dist[next_pos] == next_dist) {
				path[next_pos].emplace_back(cur_pos);
			}
		}
	}

	//최단 경로를 역추적하면서 가중치를 INF로 바꿔 비활성화
	int prev_pos;
	queue<int> q;
	q.emplace(d);
	while (!q.empty()) {
		cur_pos = q.front();
		q.pop();
		for (int i = 0; i < path[cur_pos].size(); ++i) {
			prev_pos = path[cur_pos][i];
			if (cost[prev_pos][cur_pos] < INF) {
				cost[prev_pos][cur_pos] = INF;
				q.emplace(prev_pos);
			}
		}
	}

	for (int i = 0; i < N; ++i) dist[i] = INF;

	//다시 다익스트라 알고리즘으로 최단경로 구하기
	pq.emplace(0, s);
	dist[s] = 0;
	while (!pq.empty()) {
		cur_dist = -pq.top().first;
		cur_pos = pq.top().second;
		pq.pop();

		if (dist[cur_pos] < cur_dist) continue;
		for (iter = cost[cur_pos].begin(); iter != cost[cur_pos].end(); ++iter) {
			if (iter->second == INF) continue;
			next_pos = iter->first;
			next_dist = cur_dist + iter->second;
			if (dist[next_pos] > next_dist) {
				dist[next_pos] = next_dist;
				pq.emplace(-next_dist, next_pos);
			}
		}
	}

	return dist[d] != INF ? dist[d] : -1;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int from, to, tmp_cost;

	while (1) {
		cin >> N >> M;
		if (N + M == 0) break;
		cin >> s >> d;

		for (int i = 0; i < N; i++) {
			dist[i] = INF;
			cost[i].clear();
			path[i].clear();
		}
		for (int i = 0; i < M; ++i) {
			cin >> from >> to >> tmp_cost;
			cost[from][to] = tmp_cost;
		}
		cout << dijkstra() << '\n';
	}

	return 0;
}

메모리: 2840 kb

시간: 44 ms

 

여담으로 이 문제를 풀면서 path 값을 초기화를 시켜주지 않아서 디버깅에 애를 먹었는데,

코드를 처음부터 제대로 계획하고 짠게 아니라 짜면서 미흡한 부분을 계속 고쳐나가다 보니까 이런 현상이 발생한 것 같다. 항상 문제를 풀기 전에 나름대로 이렇게 풀어야겠다 계획을 세우고 코드를 짜기 시작하는데 중간에 로직 오류가 발견되어서 고치고 고치다 스파게티 소스가 되는 경우가 많다. 아직도 많이 부족한가보다. 열심히 하자.