[백준1504] 특정한 최단 경로 (C++)

📌 문제

BOJ 바로가기
다익스트라 알고리즘 구현 연습에 좋은 문제인 것 같다. 단순 다익스트라 구현 + 약간의 아이디어가 추가된 문제이다. 최단경로를 구하되 문제에서 주어지는 두 점을 꼭 지나도록 해야 한다.

🗡 풀이

📍 1부터 N까지 특정한 두 점(a, b)을 지나는 최단경로는 다음과 같이 표현할 수 있다.

• 1 -> a -> b -> N
  혹은
• 1 -> b -> a -> N

📍 각각의 경우에 다익스트라 알고리즘을 이용해 잘게 쪼개진 경로의 최단거리를 구하고 그 합을 비교한다.

📍 이 때 갈 수 없는 경로 (dijkstra 함수의 리턴값이 INF) 인 경우는 답에서 제외해줘야 한다!

📍 처음엔 플로이드-워셜 알고리즘을 사용할까 했는데, n의 최댓값이 800인지라 시간초과가 예상되어서 다익스트라를 여러 번 구현하는 방식으로 설계했다.

🥶 잘 풀었다고 생각했는데 도저히 답이 안나와서... 멘탈 나갈 뻔했다.

• memset함수를 이용해 최단거리 테이블을 INF로 초기화해줬는데, 자꾸만 이상한 값이 나왔다. 지금까지 잘 써먹어서 이것 때문이었을 줄은 몰랐다.. 😭
• 인덱스 1부터 시작인데 까먹고 자꾸 0을 넣는 바람에 또 한세월 걸렸다..

꼼꼼한 사람 되고싶다 😭 계속 풀다보면 디버깅도 늘겠지..

🚩 소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define INF 987654321
using namespace std;

int n, d[801];
vector<pair<int, int>> node[801];

int dijkstra(int x, int y) {
	for (int i = 1; i <= n; i++)
		d[i] = INF;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0, x });
	d[x] = 0;
	while (!pq.empty()) {
		int dist = pq.top().first;
		int curr = pq.top().second;
		pq.pop();
		for (int i = 0; i < node[curr].size(); i++) {
			int ndist = node[curr][i].first;
			int ncurr = node[curr][i].second;
			if (d[ncurr] > dist + ndist) {
				d[ncurr] = dist + ndist;
				pq.push({ d[ncurr], ncurr });
			}
		}
	}
	return d[y];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int e, v1, v2, dist = 0, ans1 = 987654321, ans2 = 987654321;
	cin >> n >> e;
	for (int i = 0; i < e; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		node[a].push_back({ c, b });
		node[b].push_back({ c, a });
	}
	cin >> v1 >> v2;
	// 1 -> V1 -> V2 -> N 끊기는 부분 있는지 체크
	if (dijkstra(1, v1) == INF || dijkstra(v1, v2) == INF || dijkstra(v2, n) == INF)
		ans1 = INF;
	else
		ans1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, n);
	// 1-> V2 -> V1 -> N 끊기는 부분 있는지 체크
	if (dijkstra(1, v2) == INF || dijkstra(v2, v1) == INF || dijkstra(v1, n) == INF)
		ans2 = INF;
	else
		ans2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, n);
	// 정답 출력
	if (ans1 == INF && ans2 == INF)
		cout << "-1";
	else
		cout << min(ans1, ans2);
}