[ DP - 11404 ] 플로이드(C++)

 

---

접근법

 

최단경로 찾기에 적용 가능한 Dynamic Programming Algorithm이 바로 Floyd(플로이드)이다.

 

문제를 보면 특정 도시에서 다른 도시로 가는 서로다른 비용을 가지는 버스가 존재하고, 특정 도시에서 다른 도시로 가는 최소 비용을 구하는 문제이다. 따라서 주어진 문제(경로에 따른 비용)에 대하여 하나 이상의 많은 해가 존재할 때, 최적의 해답을 찾아야 하는 최적화 문제이다. 

 

우리는 주어진 정보 중 출발 도시와 도착 도시 사이의 최소 cost를 원소로 가지는 인접 행렬식 $W$를 포현할 수 있다. 예를들어, $W[i][j]& 는 $i$에서 $j$로 가는 최소 비용을 의미한다. 만약 $i$에서 $j$로 가는 버스가 없다면, 구해야 하는 것은 최소 비용이기 때문에 무한대로 표현하고, $i==j$이면 0으로 설정해야 한다.

 

그렇다면 우리가 고려해야 하는 것은 결국 $i$에서 $j$로 바로 가는 비용과, $ 1 \leq k \leq n$(n은 도시의 수) 범위의 $k$에 대하여 $i$에서 $k$로 간 뒤, $k$에서 $j$로 가는 비용을 비교하면 된다. 이러한 최소 비용을 저장하는 Matrix를 $D^k, 1 \leq k \leq n$이라 한다. 

 

 

 

다음과 같이 문제가 주여졌다고 하자. $i$번째 도시를 $V_i$로 표현하여 각 그래프의 노드로 나타냈으며, 각 도시간 이동에 필요한 비용을 간선으로 표현하였다. $W$ Matrix를 구하면 다음과 같다.

 

 

k 도시를 거쳤을 때를 고려한 최소 비용을 나타내는 그래프는 $D^k$이므로, 결국 $D^0 = W, D^n = D$가 될 것이다. 따라서 $D$를 구하기 위해서는 $D^0$를 이용하여 $D^n$을 구하는 방법을 고안해야 한다.

 

앞에서 이미 재귀 관계식을 도출하기 위한 관계를 말로 설명하였다.

 

우리가 고려해야 하는 것은 결국 $i$에서 $j$로 바로 가는 비용과, $ 1 \leq k \leq n$(n은 도시의 수) 범위의 $k$에 대하여 $i$에서 $k$로 간 뒤, $k$에서 $j$로 가는 비용을 비교하면 된다. 

 

따라서 이를 수식화 한다면 아래와 같다.

$$D^k[i][j] = minimum(D^{k-1}[i][j], D^{k-1}[i][k] + D^{k-1}[k][j])$$

 

이제 구현 해 보자.

 

---

정답

#pragma warning(disable:4996)
#include <iostream>
#include <cstdlib>
#define C_INFINITE 100000000 // 매우 큰 값 

using namespace std;

int DP[101][101];

int main() {
    int n, m, i, j, k;
    int cin1, cin2, cost;
    scanf("%d %d", &n, &m);

    // i == j -> 내가 내 위치로 가는 과정 -> 0
    // 아니면 무한대로 설정 -> Minimum Cost를 구해야 하기 때문
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            DP[i][j] = (i == j) ? 0 : C_INFINITE;
        }
    }

    // i->j로 가는 버스의 cost로 갱신
    for (i = 0; i < m; i++) {
        scanf("%d %d %d", &cin1, &cin2, &cost);
        if (DP[cin1][cin2] > cost)
            DP[cin1][cin2] = cost;
    }

    // D^1~D^n 계산
    for (k = 1; k <= n; k++) {
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                DP[i][j] = (DP[i][j] < (DP[i][k] + DP[k][j])) ? DP[i][j] : DP[i][k] + DP[k][j];
            }
        }
    }

    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (DP[i][j] == C_INFINITE)
                DP[i][j] = 0;
            printf("%d ", DP[i][j]);
        }
        printf("\n");
    }

    return 0;
}

   

 

결국, 앞서 언급한 점화식은 아래와 같이 구현할 수 있다.

 

    for (k = 1; k <= n; k++) {
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                DP[i][j] = (DP[i][j] < (DP[i][k] + DP[k][j])) ? DP[i][j] : DP[i][k] + DP[k][j];
            }
        }
    }

 

k에 대한 for문이 가장 바깥쪽에서 고려되어야 정확한 계산이 가능함을 주의하자.

 

위 문제에 대한 실행 결과

 

다음과 같이 각 도시에 대하여 이동했을 때의 최소 비용은 문제와 같다.

 

백준 문제에 대한 정답은 

 

 

다음과 같이 잘 나옴을 확인할 수 있다.