백준9370번(미확인 도착지)[C/C++]

🔗링크

1. 문제 풀이

문제에 대한 이해가 부족한 상태로 풀다가 시간을 많이 낭비한 문제이다,,

이 문제의 핵심은 주어진 특정 경로가 후보지로 가는 최단경로(유일 또는 여러개 존재)에 포함이 되는가를 확인하는 것이다.

간단한 그림으로 설명하자면

---

시작점은 2, g = 1, h = 3, 후보지는 5,6인 문제는 아래와 같다.

---

여기서 경로 g-h를 제외한 후 각 후보지의 최단거리를 구하면 다음과 같다.

---

그 후 특정 후보지까지의 최단경로에 g-h가 포함되는가를 확인하기 위해
g-h를 강제로 포함한 경로와 포함되지 않은 경로를 비교한다.

즉 정점 6까지의 최단경로는 g-h가 포함되어 있기에 후보지 목록에 유지
정점 5의 최단경로엔 g-h가 포함되지 않기에 후보지 목록에서 제외된다.

특정 경로 g-h를 강제로 포함시키기 위해선
(S = 시작점, E = 목적지)
S -> (g -> h) -> E
S -> (h -> g) -> E 둘 중
작은 값을 취하면 되고

이는 곧
MIN(g->S + g->h + h->E, h->S + h->g + g->E)를 구하면 된다.

최단 경로를 구하는 알고리즘은 다익스트라를 사용하였다.

이때 inf의 범위를 지정할 때 주의해야 할 것이
inf를 너무 크게 지정할 시
g->S + g->h + h->E에서 언더플로우가 발생하여 음수값이 됨으로
inf값을 연산시 정수형의 범위를 벗어나지 않도록 지정해 주어야 한다(여기서 삽질 많이함,,).

---

2. 코드

#include<stdio.h>
#include<vector>
#include <algorithm>
using namespace std;
#define inf 10e7

int G[2001][2001], V[3][2001], D[3][2001], n, m, t;
vector<int> res;
int min(int a, int b) { return (a < b) ? a : b; }

int find_next(int s) {
	int v = -1, w = inf;
	for (int i = 1; i <= n; i++)
		if (D[s][i] < w && !V[s][i]) {
			w = D[s][i];
			v = i;
		}
	return v;
}

void Dijkstra(int s) {
	int v;
	while ((v = find_next(s)) != -1) {
		V[s][v] = 1;
		for (int i = 1; i <= n; i++)
			if (G[v][i] != inf&&D[s][i] > G[v][i] + D[s][v])D[s][i] = G[v][i] + D[s][v];
	}
}

void init() {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (i == j)G[i][j] = 0;
			else G[i][j] = inf;
	res.clear();
}


int main() {
	int T, s, g, h, a, b, w, x,tmp;

	scanf("%d", &T);
	while (T--) {
		scanf("%d%d%d%d%d%d", &n, &m, &t, &s, &g, &h);
		init();
		for (int i = 0; i < m; i++) {
			scanf("%d%d%d", &a, &b, &w);
			G[b][a] = G[a][b] = w;
		}
		for (int i = 1; i <= n; i++) {
			D[0][i] = G[s][i];
			D[1][i] = G[g][i];
			D[2][i] = G[h][i];
			V[0][i] = V[1][i] = V[2][i] = 0;
		}
		tmp = G[g][h];
		G[g][h] = G[h][g] = D[0][h] = D[0][g] = inf;
		Dijkstra(0);

		G[g][h] = G[h][g] = tmp;
		Dijkstra(1);
		Dijkstra(2);

		for (int i = 0; i < t; i++) {
			scanf("%d", &x);
			if (D[0][x] >= min(D[1][s] + G[g][h] + D[2][x], D[2][s] + G[g][h] + D[1][x]))
				res.push_back(x);
		}
		sort(res.begin(), res.end());
		for (auto i = res.begin(); i != res.end(); i++) printf("%d ", *i);	
		printf("\n");
	}
	return 0;
}

3. 후기

피드백
1. 문제 꼼꼼히 읽고 이해한 후 풀기
2. 주어진 범위에 대해 여러 경우들 고려하기
3. 뇌빼고 풀지 않기