[Floyd] BOJ 1602 도망자 원숭이

문제 링크 : www.acmicpc.net/problem/1602

1602번: 도망자 원숭이

문제에서 쿼리 형식으로 출발, 도착 노드에 대한 최소 시간을 묻고 있으므로,

모든 노드에 대해 다른 모든 노드까지의 최단경로를 구하는 플로이드-와샬 알고리즘이 적절할 것이다.

 

다만 도시 별 괴롭힘 시간이라는 별도의 가중치가 존재하는데,

멍멍이는 원숭이가 지나는 경로 중 가장 괴롭힘 시간이 긴 도시에서 괴롭히게 된다.

다만, 플로이드-와샬 알고리즘을 단순히 적용하려 할 때, 다음과 같은 문제가 발생한다.

도시의 괴롭힘 시간을 최단거리 계산 중에 적용할 경우, 위 그림의 오른쪽 예시에서 올바른 답을 구할 수 없다. 

오른쪽 예시의 실제 최단경로는 1-4-2-3 이지만, 1-4-2 경로에 대한 가중치 정보가 dist[1][2]를 구할 때의 min 연산에 의해 사라지기 때문이다. (1-2 경로의 가중치는 15로, 1-4-2 경로보다 더 작다.)

하지만 그렇다고 우선 도시의 가중치를 배제하고 최단거리를 구한 후 나중에 적용하려고 하면,

위 그림에서 왼쪽 예시에 대해 올바른 답을 구할 수 없다.

단순히 간선의 가중치로는 왼쪽 예시에서 1-2-4 경로가 100으로 최단경로이기 때문이다.

 

따라서, 플로이드-와샬 알고리즘에서 middle 노드를 정할 때 특정 기준을 세워야 한다.

이 문제에서는 도시의 괴롭힘 시간이 적은 순서대로 middle 노드로 둔다.

우선 가중치가 적은 도시가 middle이 되는 경로로 먼저 dist 배열을 채운 뒤, (이는 일반적으로 최단경로가 될 가능성이 높다.)

가중치가 더 높은 도시를 middle로 하였을 때 (이를 예외 케이스로 두어 확인한다고 이해하면 된다.)

dist값이 더 작다면 그 값으로 덮어씌운다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
#define INF 999999999
 
using namespace std;
typedef pair<int, int> p;
 
int n, m, q;
int dist[501][501], wait[501][501];
vector<p> order;
 
void floyd() {
    for (int middle = 0; middle < n; middle++) {
        p mid = order[middle];
        for (int start = 1; start <= n; start++) {
            for (int end = 1; end <= n; end++) {
                int midnode = mid.second;
                int newWait = max(mid.first, wait[start][end]);
 
                int newDist = (dist[start][midnode] - wait[start][midnode]) 
                    + (dist[midnode][end] - wait[midnode][end]) + newWait;
 
                if (dist[start][end] > newDist) {
                    dist[start][end] = newDist;
                    wait[start][end] = newWait;
                }
            }
        }
    }
}
 
void init() {
    int f, s, w;
    cin >> n >> m >> q;
 
    for (int i = 1; i <= n; i++) {
        cin >> w;
        wait[i][i] = w;
        order.push_back({ w, i });
    }
 
    sort(order.begin(), order.end());
 
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++) {
            dist[i][j] = INF;
            wait[i][j] = max(wait[i][i], wait[j][j]);
        }
    }
 
    for (int i = 1; i <= n; i++) dist[i][i] = wait[i][i];
 
    for (int i = 0; i < m; i++) {
        cin >> f >> s >> w;
        int mwait = max(wait[s][s], wait[f][f]);
        dist[f][s] = w + mwait;
        dist[s][f] = w + mwait;
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    int s, e;
 
    init();
    floyd();
 
    for (int i = 0; i < q; i++) {
        cin >> s >> e;
        int distval = dist[s][e];
        if (distval >= INF) printf("-1\n");
        else printf("%d\n", distval);
    }
 
    return 0;
}

 

[이 문제에서 얻을 수 있는 것]

플로이드-와샬 알고리즘에서 정점 방문 순서를 변경하는 기법