[BOJ] 1504 특정한 최단 경로

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

7

---

문제를 보고 바로 다익스트라를 3번 적용하면 풀 수 있겠다 싶었다.

1에서 v1, v1에서 v2, v2에서 N. 이렇게 3번 적용했다.

 

저번엔 다익스트라를 심플하게 구현해서 이번엔 우선순위 큐를 사용해봤다.

다 푼 거 같은데 자꾸 7%에서 틀렸다.

 

자꾸 틀리던 이유 첫 번째는 v1과 v2는 순서가 정해져 있지 않다.

따라서 1->v2->v1->N도 후보에 올려야 한다.

이렇게 코드를 수정하고 나니 또 다른 문제가 있었다.

경로가 하나뿐이라고 생각해서 각 부분 경로를 구할 때마다 경로가 없으면 -1을 출력했는데

다른 경로는 또 될 수 도 있으니 이걸 처리해줘야 했다.

 

근데 이걸 처리해도 7%에서 계속 틀렸다. 그래서 질문 게시판에서 반례를 뒤져서 몇 개 돌려봤는데 

https://www.acmicpc.net/board/view/53375

글 읽기 - [python][다익스트라] 반례를 못찾겠습니다 부탁드립니다

여기에 다른 분이 올려주신 반례가 도움이 됐다. 8이 출력되어야 하는데 자꾸 10이 나왔다.

그 이유는 dist 배열을 초기화할 때 mat[start][i]로 초기화했는데 그게 아니라 INF 값으로 초기화했어야 했다.

우선순위 큐를 사용하지 않을 때에는 이렇게 해도 상관없는데 우선순위 큐를 사용하면서 visit 배열이 삭제되고

이런 문제가 발생한 것 같다.

 

INF로 초기화하고 나니 마의 7%는 넘겼는데 100%에서 또 틀렸다.

이건 마지막에 result 값을 INF랑 비교할 때 =가 없어서 생긴 문제였다.

 

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

const int INF = 7654321;
int N, E;
int v1, v2;
int mat[1001][1001];
int dist[1001];

int Dijkstra(int start, int end) {
	if (start == end) return 0;
	
	for (int i = 1; i <= N; i++)
		dist[i] = INF;

	std::priority_queue<std::pair<int, int>> pq;

	pq.push({ 0, start });
	dist[start] = 0;

	while (!pq.empty()) {
		int cost = -pq.top().first;
		int cur = pq.top().second;

		pq.pop();

		for (int i = 1; i <= N; i++) {
			if (dist[i] > dist[cur] + mat[cur][i]) {
				dist[i] = dist[cur] + mat[cur][i];
				pq.push({ -dist[i], i });
			}
		}
	}
	
	return dist[end];
}

int main() {
	std::cin >> N >> E;
	
	for (int i = 1; i <= N; i++)
		for(int j = 1; j <= N; j++)
			mat[i][j] = INF;

	int a, b, c;
	for (int i = 0; i < E; i++) {
		std::cin >> a >> b >> c;
		mat[a][b] = c;
		mat[b][a] = c;
	}

	std::cin >> v1 >> v2;

	int sum1 = 0;
	int sum2 = 0;
	int result;
	
	result = Dijkstra(1, v1);
	sum1 += result;
	
	result = Dijkstra(v1 ,v2);
	sum1 += result;
	
	result = Dijkstra(v2, N);
	sum1 += result;

	//------------------------------

	result = Dijkstra(1, v2);
	sum2 += result;

	result = Dijkstra(v2, v1);
	sum2 += result;

	result = Dijkstra(v1, N);
	sum2 += result;

	result = std::min(sum1, sum2);

	if (result >= INF) std::cout << -1;
	else std::cout << result;

	return 0;
}

 

후기) 

문제를 잘 읽자. 학기 중에도 문제를 대충 읽어서 실수하는 경우가 많았다.

근데 자주 반복되는 실수는? 실력이다~

heap을 사용하는 다익스트라까지는 구현해봤는데 C++ 우선순위 큐로는 처음 구현해봤다.

visit을 사용하면 안되는건 좀 신기했다.

 

다른 분들이 푼 코드를 보면 플로이드를 사용한 분들도 있었다.

플로이드를 쓰면 안되는 문제를 보면 플로이드가 떠오르는데

왜 정작 필요할 때는 생각이 안 나는 걸까? ㅋㅋ;