boj, 백준) 5719. 거의 최단 경로( C / C++ )

1. 문제 링크

www.acmicpc.net/problem/5719

5719번: 거의 최단 경로

2. 문제 개요

주어진 도로의 거의 최단경로를 구하자. 거의 최단경로는 최단경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 

 

3. 문제 힌트

최단경로를 제거해야 하기 때문에, dijkstra 최단경로 알고리즘을 1회 실행하자.

이때, O(n^2)가 아닌 log형태인 우선순위 큐를 사용해야 함. (시간 초과)

 

거리 값이 갱신될 때, 경로 값을 저장하자.

 

그 후 , BFS를 사용하여 도착점-> 시작점으로 경로를 제거해주자.

 

다시 dijkstra 최단경로 알고리즘을 1회 실행.

 

 

4. 문제 풀이

우선, 풀이에 앞서 계속 메모리 초과가 나와서 고생하는 분들께 바치는 풀이이다..

 

위의 힌트의 내용은 이미 알고 있다고 가정하겠습니다.

 

특별한 부분은, 우선순위 큐를 사용한 다익스트라 알고리즘인데, 보통

{최단경로[next] > 최단경로[cur] + 가중치[cur][next]} 이런 식으로 값을 비교하여 queue에 삽입할 것이다.

그런데, 최단경로가 여러 개 있을 수 있으므로, {최단경로[next] == 최단경로[cur] + 가중치[cur][next]} 인 경우도 생각하여 경로를 추가시켜줘야 한다는 점을 잊지 말자.

 

그리고.. 메모리 초과 5~6번을 나게 한.... BFS함수 부분인데..

 

처음에는 당연히 중복은 이루어질 거라 예상했지만 이게 cycle이 있어 메모리가 초과할 때까지 중복되리라는 생각 못했다.

 

그래서 간선들에 대해 visited배열을 만들어서 두 번 방문하지 않도록 했지만.. 메모리 초과,

이렇게 하면 당연히 메모리 초과가 안 날거라 생각했지만 메모리 초과가 나와서 다익스트라 함수를 잘못 구현했나.. 싶어서 건드려보고, 전역 함수를 초기화하는데 잘못 초기화했나.. 하다가 이것저것 건드려보다가

 

BFS함수에서 간선에 대해 visited배열을 만들지 말고 정점에 대해 visited배열을 만들면 확실히 어딘가에 순환이 일어나지 않을 거라 판단하고 구현해보니 바로 통과가 되었다. 조금 허무하긴 했지만.. 왜 바로 생각 못했을까 싶었다..

 

google에 풀이가 꽤나 있었지만, 모두 옛날 풀이고 채점 결과를 찾아보니 모두 재채점으로 인해서 다 오답이 많았다.  그래서 풀이를 업로드했고 저와 같은 경우로 시간을 허비하시는 분이 없었으면..

 

그리고 구현했던 다익스트라 함수를 한번 더 호출해서 출력하자.

 

 

5. 코드

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;

struct ITEM {
	ITEM(){}
	ITEM(int node, int dist_) : node(node), dist(dist_) {}

	bool operator <(const ITEM & other) const{
		return this->dist > other.dist;
	}
	int  node, dist;	//dist : node에 도달하기까지의 거리.
};

const int INF = 987654321;
int n, m, ans;
int src, dst;
int adj[500][500];
vector<int> dist,parent[500];

int dijkstra() 
{
	priority_queue<ITEM> pq;
	fill(dist.begin(), dist.end(), INF);
	
	pq.push(ITEM(src, 0));
	dist[src] = 0;

	while (!pq.empty()) 
	{
		ITEM cur = pq.top(); pq.pop();

		if (cur.dist > dist[cur.node])
			continue;

		for (int i = 0; i < n; ++i) {
			
			if (adj[cur.node][i] != 0 && dist[i] > dist[cur.node] + adj[cur.node][i]) {
				dist[i] = dist[cur.node] + adj[cur.node][i];
				parent[i].clear();
				parent[i].push_back(cur.node);
				pq.push(ITEM(i,dist[i]));
			}
			else if (adj[cur.node][i] != 0 && dist[i] == dist[cur.node] + adj[cur.node][i]) {
				parent[i].push_back(cur.node);
			}
		}
	}

	return dist[dst]; 
}

void remove_path()
{
	queue<int> q;
	q.push(dst);
	bool visited[500] = { false, };
	visited[dst] = true;
	while (!q.empty()) 
	{
		int cur = q.front(); q.pop();

		for (int p : parent[cur]) {

			adj[p][cur] = 0;

			if (!visited[p]) {
				q.push(p);
				visited[p] = true;
			}
		}
	}
	
	return;
}

int main()
{
	scanf("%d %d", &n, &m);

	while (!(n == 0 && m == 0))
	{
		scanf("%d %d", &src, &dst);
		
		memset(adj, 0, sizeof(adj));
		dist.resize(n);
		
		for (int i = 0; i < n; ++i)
			parent[i].clear();

		for (int i = 0; i < m; ++i) {
			int from, to, weight;
			scanf("%d %d %d", &from, &to, &weight);
			adj[from][to] = weight;
		}

		ans = dijkstra();
		remove_path();
		ans = dijkstra();

		if (ans == INF)
			printf("-1\n");
		else
			printf("%d\n", ans);
		
		scanf("%d %d", &n, &m);
	}

	return 0;
}

 

6. 결과