[AtCoder] Jumping Takahashi 2

https://atcoder.jp/contests/abc257/tasks/abc257_d

D - Jumping Takahashi 2

처음에 나는 BFS 방식을 시도하였으나 시간 초과가 발생하였다. 그러나 스터디를 하면서 플로이드 와샬 알고리즘을 이용하면 빠르게 풀 수 있다는 소식을 접했다.

지금까지 자주 풀어보았던 다익스트라 알고리즘은 한 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다.

반면 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 와샬 알고리즘을 사용해야 한다.

 

다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면 플로이드 와샬 알고리즘은 기본적으로 '거쳐가는 정점'을 기준으로 알고리즘을 수행한다는 점에서 그 특징이 있다.

 

또한 플로이드 와샬은 기본적으로 다이나믹 프로그래밍(DP)에 의거한다.

플로이드 와샬 알고리즘의 핵심 아이디어는 '거쳐가는 정점'을 기준으로 최단 거리를 구하는 것이다.

#include <iostream>
#include <cmath>
using namespace std;
long long t[200][200];
int x[200];
int y[200];
int p[200];
int main() {
    int n;
    cin >> n;
    for(int i = 0;i < n;i++) {
        cin >> x[i] >> y[i] >> p[i];
    }
    // i에서 j까지
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            if(i == j) {
                continue;
            }
            t[i][j] = ceil((fabs(x[i] - x[j]) + fabs(y[i] - y[j])) / (float) p[i]);
        }
    }
    
    for(int m = 0;m < n;m++) {
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < n;j++) {
                if(i == j || j == m || i == m) continue;
                long long value = max(t[i][m], t[m][j]);
                t[i][j] = min(t[i][j], value);
            }
        }
    }
    long long answer = -1;
    for(int i = 0;i < n;i++) {
        long max_value = 0;
        for(int j = 0;j < n;j++) {
            max_value = max(t[i][j], max_value);
        }
        if(answer == -1 || answer > max_value) {
            answer = max_value;
        }
    }
    
    cout << answer << '\n';
    return 0;
}

이렇게 코드로 보니 사실 최근에 많이 풀었던 유형이었다...플로이드 와샬이라는 명칭을 까먹었을 뿐..ㅎㅎ...

그리고 혼자 풀 때도 이러한 방법으로 접근했었는데 한 가지 간과한 점이 있었다. 트램펄린은 linear하게 있지않다는 점이다.

난 i, j의 사이값만 중간 트램펄린으로 넣었는데, 그러면 안됐다...ㅎㅎ

 

모든 트램펄린은 일종의 그래프의 노드이기 때문에 그냥 모든 노드 간의 거리를 계산해줘야 했다.

대신 중간 노드, 출발 노드, 종료 노드는 서로 하나라도 같으면 안된다.

 

저 코드로만 보면 헷갈리니 pseudo code를 같이 올려본다.

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each edge (u,v)
3    dist[u][v] ← w(u,v)  // 변 (u,v)의 가중치
4 for each vertex v
5    dist[v][v] ← 0
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j]
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if

여기서 3중 루프의 순서를 헷갈리면 안된다.

중간 노드 - 출발 & 도착 노드로, 중간노드가 양 끝 노드를 감싸야 한다. 이를 통해 최소 경로를 갱신한다.

 

참고

https://ansohxxn.github.io/algorithm/floyd/

(C++) 플로이드 와샬 Floyd Warshall (+ 최단 경로 알고리즘 비교)