7. 최단 경로 알고리즘 - 시간여행(timetrip) 문제

문제를 해결하기 위해 각 은하계를 정점으로 하고, 은하계 사이를 이동하는 웜홀들을 간선으로 하는 그래프를 모델링할 수 있다.

지구는 0번 은하계, 안드로메다는 1번 은하계이므로 문제는 0번 정점에서 1번 정점까지 가는 최단 경로를 구하는 문제가 된다.

가장 빠른 시간뿐만 아니라 가장 늦은 시간도 구해야 하기 때문에 최장 경로의 길이도 구해야 하는데,

이는 lower[] 배열을 하나 더 만들어서 하한선에서 완화 과정을 통해 값을 증가시켜나가는 방법도 있고,

각 웜홀의 이동시간에 대해 모두 부호를 반대로 바꿔서 최단 경로 알고리즘을 한번 더 수행하는 방법도 있다.

그런데 경우에 따라 안드로메다로 도달할 수 없는 경우도 있고, 무한한 과거나 미래로 갈 수 있는 경우가 있다.

무한한 과거나 미래로 가는 경우는 음수 사이클이나 양수 사이클을 찾아내야 하는데,

이 사이클들을 거쳐서 안드로메다로 갈 수 있는 경로가 존재하는지를 따로 확인해야 한다.

즉, reachable[][] 이라는 한 정점에서 다른 정점으로 갈 수 있는 경로의 존재 여부를 저장하는 배열을 만들어서,

시작점부터 사이클안에 존재하는 정점까지의 경로와 이 정점부터 종료점까지의 경로가 모두 존재하면 무한히 과거나 미래로 가게 된다는 것을 판단 할 수 있다.

// 시간여행 문제를 해결하는 벨만-포드 알고리즘

#include <iostream>

#include <vector>

#include <string>

using namespace std;

vector< pair<int, int> > adj[100];

bool reachable[100][100];

const int INF = 987654321;

string trip(int start, int finish, int v) {

vector<int> upper(v, INF);

vector<int> lower(v, -INF);

upper[start] = 0;

lower[start] = 0;

for (int iter = 0; iter < v - 1; iter++) {

for (int here = 0; here < v; here++) {

for (int i = 0; i < adj[here].size(); i++) {

int there = adj[here][i].first;

int cost = adj[here][i].second;

// upper 완화 시도

if (upper[there] > upper[here] + cost) {

upper[there] = upper[here] + cost;

}

// lower 완화시도

if (lower[there] < lower[here] + cost) {

lower[there] = lower[here] + cost;

}

}

}

}

string ret;

bool upInfinity = false;

bool loInfinity = false;

for (int here = 0; here < v; here++) {

for (int i = 0; i < adj[here].size(); here++) {

int there = adj[here][i].first;

int cost = adj[here][i].second;

if (upper[there] > upper[here] + cost) {  // 완화 성공하고 해당 정점을 통해 종료점으로 가는 경로가 있으면 infinity

if (reachable[start][here] && reachable[here][finish]) upInfinity = true;

}

if (lower[there] < lower[here] + cost) {

if (reachable[start][here] && reachable[here][finish]) loInfinity = true;

}

}

}

if (upper[finish] >= INF - 98765432) return "UNREACHABLE";

if (upInfinity && loInfinity) ret = "INFINITY INFINITY";

else if (upInfinity) ret = "INFINITY " + to_string(lower[finish]);

else if (loInfinity) ret = to_string(upper[finish]) + " INFINITY";

else ret = to_string(upper[finish]) + " " + to_string(lower[finish]);

return ret;

}

int main() {

int c;  // 테스트 케이스 수

vector<string> result;

cin >> c;

for (int test = 0; test < c; test++) {

int v, w;  // 은하계의 수와 웜홀의 수

cin >> v >> w;

for (int i = 0; i < w; i++) {

int a, b, c;

cin >> a >> b >> c;

adj[a].push_back(make_pair(b, c));

reachable[a][b] = true;

}

for (int i = 0; i < v; i++) {

for (int j = 0; j < v; j++) {

if (i == j) reachable[i][j] = true;

}

}

for (int i = 0; i < v; i++) {

for (int j = 0; j < v; j++) {

for (int k = 0; k < v; k++) {

reachable[j][k] = reachable[j][k] || (reachable[j][i] && reachable[i][k]);

}

}

}

string res = trip(0, 1, v);

result.push_back(res);

for (int i = 0; i < v; i++) {

adj[i].clear();

}

}

for (int i = 0; i < c; i++) {

cout << result[i] << endl;

}

return 0;

}

위 코드에서 1번 정점에 도달할 수 있는지 여부를 판단할 때 무조건 upper[1] 이 INF와 같은지 비교하지 않는다.

그래프에서 1번 정점으로 향하는 간선들 중 음수 가중치가 있는 경우,

완화 과정이 반복될 때 마다 upper[1] 의 값이 INF-k 식으로 감소하게 될 수 있다.

따라서, 적당히 큰 값 M(위에서는 98765432) 에 대해 upper[1] >= INF - M 을 만족하는지를 확인해야 한다.