[99클럽/코딩테스트 챌린지/C++] "특정한 최단 경로" 문제 해결 과정

문제 링크:

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

문제 상황

오늘 해결한 문제는 방향성이 없는 그래프에서 특정한 두 정점을 반드시 거치는 최단 경로를 찾는 문제였습니다. 주어진 그래프는 NNN개의 정점과 EEE개의 간선으로 구성되며, 출발점(1번 정점)에서 도착점(NNN번 정점)까지 이동하는 경로 중 V1V1V1과 V2V2V2라는 특정 정점을 반드시 통과해야 했습니다. 이때 최단 경로의 길이를 구하는 것이 목표였습니다.

• 제약 조건:
  • 간선이 없는 경우 또는 특정 경로가 없는 경우 결과는 −1-1−1을 출력.
  • 정점은 최대 800개, 간선은 최대 200,000개로 매우 큰 입력을 처리해야 함.

---

문제 원인

문제를 해결하면서 겪은 주요 문제점은 다음과 같습니다:

1. 간선이 없는 경우에 대한 예외 처리 부족: E=0E = 0E=0일 경우 경로가 존재하지 않으므로 즉시 −1-1−1을 출력해야 했으나, 이를 고려하지 않아 오류가 발생했습니다.
2. 경로 비교 로직 누락: 1→V1→V2→N1 \to V1 \to V2 \to N1→V1→V2→N 경로와 1→V2→V1→N1 \to V2 \to V1 \to N1→V2→V1→N 경로를 모두 계산해야 했으나, 이를 명확히 처리하지 않아 틀린 결과가 나올 수 있었습니다.

---

최종 코드

#include <algorithm>
#include <iostream>
#include <queue>

#define MAX 805
#define INF 1000000000
int N, E;
int dist[MAX][MAX];
int V1, V2;
using namespace std;

int findNav(int start,int end)
{
	priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int, int>>> pq;
	pq.push({0,start });
	vector<int> distance = vector<int>(N + 1, INF);
	distance[start] = 0;

	while (pq.empty() == false)
	{
		pair<int,int> currentDist = pq.top();
		pq.pop();

		int cur = currentDist.second;
		int cost = currentDist.first;

		// 이미 더 적은 비용으로 처리되었으면 스킵
		if (cost > distance[cur]) continue;

		for (int i = 1; i <= N; i++)
		{
			if (dist[cur][i] == INF) continue;
			if (dist[cur][i] == 0) continue;
			int newCost = cost + dist[cur][i];
			if (newCost < distance[i])
			{
				distance[i] = newCost; // 최단 거리 갱신
				pq.push({ newCost ,i });
			}
		}
	}
	return distance[end];
}

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

	std::cin >> N >> E;

	if (E <= 0)
	{
		cout << -1 << '\n';
		return 0;
	}

	for (int y = 1; y <= N; y++)
	{
		for (int x = 1; x <= N; x++)
		{
			dist[y][x] = (x == y) ? 0 : INF;
		}
	}

	for (int i = 0; i < E; i++)
	{
		int start, end, dis = 0;
		std::cin >> start >> end >> dis;
		dist[start][end] = dis;
		dist[end][start] = dis;
	}
	std::cin >> V1 >> V2;

	// 경로 1: 1 -> V1 -> V2 -> N
	long long path1 = findNav(1, V1) + findNav(V1, V2) + findNav(V2, N);

	// 경로 2: 1 -> V2 -> V1 -> N
	long long path2 = findNav(1, V2) + findNav(V2, V1) + findNav(V1, N);

	// 경로가 없는 경우 처리
	if (path1 >= INF && path2 >= INF) {
		cout << -1 << '\n';
	}
	else {
		cout << min(path1, path2) << '\n';
	}

	return 0;
}

---

배운 점

1. 문제의 예외 상황을 꼼꼼히 처리하는 방법: 간선이 없거나 특정 경로가 존재하지 않을 때의 예외 처리가 매우 중요하다는 점을 실감했습니다.

---

결론

이번 문제는 다익스트라 알고리즘의 기본 개념과 효율적인 그래프 구현 방식을 다시 복습하는 좋은 기회가 되었습니다. 특히, 경로가 없는 경우와 같은 예외 상황을 꼼꼼히 처리하는 것이 중요하다는 것을 알게 되었습니다. 앞으로 그래프 문제를 해결할 때 제약 조건을 더욱 면밀히 분석하여 적합한 구현 방식을 선택해야겠습니다. 😊