문제 : https://www.acmicpc.net/problem/9370
서론
최단경로 문제이므로 다익스트라로 접근했다.
이 문제는 풀이 아이디어가 두개다
하나는 다익스트라를 두번 사용하는 방법이고
또 다른 하나는 다익스트라를 세번 사용하는 방법이다.
테스트케이스가 여러개라서 매번 간선을 초기화해줘야하는데 초기화하는 부등호를 <=가 아닌 <로 적는 실수를 해서 원인을 찾느라 고생했다.
원인을 찾는 과정에서 다른분들의 코드를 보며 계속 수정하다보니 결국 다른분들의 코드와 아이디어가 같아졌다.
이렇게 같아진 아이디어가 다익스트라를 세번 사용하는 방법이다.
그리고 기존의 다익스트라를 두번 사용하는 방법에서 간선 초기화를 고쳤더니 잘 동작했다.
풀이
1. 다익스트라 세번 사용
문제가 길지만 요약하자면
시작지점에서 목적지 후보로 최단경로를 통해 갈건데, 이 최단경로에 간선 GH가 포함된 목적지 후보만 출력하라이다.
간선 GH를 반드시 포함하라고 하니
갈 수 있는 방법은
S->G->H->T
S->H->G->T
두가지다.
즉 목적지 후보 T에 대해
S->T까지의 최단거리 = S->G까지의 최단거리 + G->H까지의 최단거리 + H->T까지의 최단거리
가 성립하거나
S->T까지의 최단거리 = S->H까지의 최단거리 + H->G까지의 최단거리 + G->T까지의 최단거리
가 성립하면 간선 GH를 포함한 최단경로를 통해 도착한 것이므로 출력하면 된다.
그리고 위의 조건이 성립하는지 알려면
S->T, S->G, G->H, H->T, S->H, H->G, G->T의 최단거리를 구해야한다.
G->H, H->G는 동일한 값이고 값을 입력받을때 얻을 수 있다. (아래 코드에서는 변수 distGH다.)
S->T, S->G는 시작점을 S로 하는 다익스트라를 돌리면 얻을 수 있다.
H->T는 시작점을 H로 하는 다익스트라를 돌리면 얻을 수 있다.
G->T는 시작점을 G로 하는 다익스트라를 돌리면 얻을 수 있다.
즉 총 세번의 다익스트라를 통해 구현할 수 있다.
2. 다익스트라 두번 사용
다익스트라를 세번 사용하는것과 마찬가지로
간선 GH를 반드시 포함하라고 하니
갈 수 있는 방법은
S->G->H->T
S->H->G->T
두가지다.
만약 S->G의 최단거리가 4이고 S->H의 최단거리가 8이면
갈 수 있는 방법은
S->G->H->T가 되어야한다.
다익스트라는 정점을 만날 때마다 최단경로를 계속 선택하면 시작점부터 끝점까지의 최단경로가 나오는 그리디알고리즘이므로 S->?에서도 최단경로를 선택해야한다.
(이 같은 아이디어로 구현했는데, 혹시 이론이 틀렸다면 이 글을 보게 될 다른분들을 위해 알려주시길 부탁드립니다.)
그 후
S->T까지의 최단거리 = S->G까지의 최단거리 + G->H까지의 최단거리 + H->T까지의 최단거리
가 성립하면 간선 GH를 포함한 최단경로를 통해 도착한 것이므로 출력하면 된다.
즉 구해야하는것은
S->mid1(G 와 H 중 S로부터 거리가 가까운 것) -> mid2(G 와 H 중 S로부터 거리가 먼 것 ) -> T 이므로
S->T까지의 최단거리 = S->mid1까지의 최단거리 + mid1->mid2까지의 최단거리 + mid2->T 까지의 최단거리다.
mid1->mid2는 G->H or H->G이고 둘은 간선 GH의 길이므로 동일한 값이고 값을 입력받을때 얻을 수 있다.
시작지점으로부터 다익스트라를 실행하면 S->T, S->mid1을 얻을 수 있고
mid2로부터 다익스트라를 실행하면 mid2->T를 얻을 수 있다.
구현
1. 다익스트라 세번 사용
//C++
#pragma warning(disable:4996)
#include <vector>
#include <queue>
#include <cstring>
#include <cstdio>
#include <algorithm>
int n, m, t, s, g, h;
int distGH;
int fromSDist[2001];
int fromGDist[2001];
int fromHDist[2001];
std::vector<std::pair<int, int>>v[2001];
std::vector<int>destination;
void input() {
for (int i = 0; i <= n; i++) v[i].clear();
scanf("%d %d %d %d %d %d", &n, &m, &t, &s, &g, &h);
for (int i = 0; i < m; i++) {
int a, b, d;
scanf("%d %d %d", &a, &b, &d);
v[a].push_back({ d, b });
v[b].push_back({ d, a });
if ((a == g && b == h) || (a == h && b == g)) distGH = d;
}
for (int i = 0; i < t; i++) {
int x;
scanf("%d", &x);
destination.push_back(x);
}
}
void dijkstra(int start, int *distArray) {
//memset(distArray, 0x7f, sizeof(distArray)*n);
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>>q;
q.push({ 0, start });
distArray[start] = 0;
while (!q.empty()) {
int d = q.top().first;
int node = q.top().second;
q.pop();
for (int i = 0, vSize = v[node].size(); i < vSize; i++) {
int nextD = v[node][i].first;
int nextNode = v[node][i].second;
if (distArray[nextNode] > d + nextD) {
distArray[nextNode] = d + nextD;
q.push({ distArray[nextNode], nextNode });
}
}
}
}
void print() {
std::sort(destination.begin(), destination.end());
for (int i = 0, size = destination.size(); i < size; i++) {
int cur = destination[i];
if (fromSDist[cur] == fromSDist[g] + distGH + fromHDist[cur]) printf("%d ", cur);
else if (fromSDist[cur] == fromSDist[h] + distGH + fromGDist[cur]) printf("%d ", cur);
}
printf("\n");
destination.clear();
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
memset(fromSDist, 0x7f, sizeof(fromSDist));
memset(fromGDist, 0x7f, sizeof(fromGDist));
memset(fromHDist, 0x7f, sizeof(fromHDist));
input();
dijkstra(s, fromSDist);
dijkstra(g, fromGDist);
dijkstra(h, fromHDist);
print();
}
}
2. 다익스트라 두번 사용
//C++
#pragma warning(disable:4996)
#include <vector>
#include <queue>
#include <cstring>
#include <cstdio>
#include <algorithm>
int n, m, t, s, g, h;
int mid1, mid2, distMid;
int toMidDist[2001];
int toEndDist[2001];
std::vector<std::pair<int, int>>v[2001];
std::vector<int>destination;
void input() {
for (int i = 0; i <= n; i++) v[i].clear();
scanf("%d %d %d %d %d %d", &n, &m, &t, &s, &g, &h);
for (int i = 0; i < m; i++) {
int a, b, d;
scanf("%d %d %d", &a, &b, &d);
v[a].push_back({ d, b });
v[b].push_back({ d, a });
if (a == g || a == h) {
if (b == g || b == h) distMid = d;
}
}
for (int i = 0; i < t; i++) {
int x;
scanf("%d", &x);
destination.push_back(x);
}
}
void toMid(int start) {
memset(toMidDist, 0x7f, sizeof(toMidDist));
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>>q;
q.push({ 0, start });
toMidDist[start] = 0;
while (!q.empty()) {
int d = q.top().first;
int node = q.top().second;
q.pop();
for (int i = 0, vSize = v[node].size(); i < vSize; i++) {
int nextD = v[node][i].first;
int nextNode = v[node][i].second;
if (toMidDist[nextNode] > d + nextD) {
toMidDist[nextNode] = d + nextD;
q.push({ toMidDist[nextNode], nextNode });
}
}
}
}
int searchNextStart(int mid) {
if (mid == g) return h;
else return g;
}
void toEnd(int mid) {
memset(toEndDist, 0x7f, sizeof(toEndDist));
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>>q;
q.push({ 0, mid });
toEndDist[mid] = 0;
while (!q.empty()) {
int d = q.top().first;
int node = q.top().second;
q.pop();
for (int i = 0, vSize = v[node].size(); i < vSize; i++) {
int nextNode = v[node][i].second;
int nextD = v[node][i].first;
if (toEndDist[nextNode] > d + nextD) {
toEndDist[nextNode] = d + nextD;
q.push({ toEndDist[nextNode], nextNode });
}
}
}
}
void print() {
std::sort(destination.begin(), destination.end());
for (int i = 0, size = destination.size(); i < size; i++) {
int cur = destination[i];
if (toMidDist[cur] == toEndDist[cur] + toMidDist[mid1] + distMid) printf("%d ", cur);
}
printf("\n");
destination.clear();
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
input();
toMid(s);
if (toMidDist[g] > toMidDist[h]) {
mid1 = h;
mid2 = g;
}
else {
mid1 = g;
mid2 = h;
}
toEnd(mid2);
print();
}
}
최근댓글