합승택시요금 분석

#include <string>
#include <vector>

using namespace std;

#define MAX 21000000
int cost[201][201];

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = MAX;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            cost[i][j] = MAX;
        }
        cost[i][i] = 0;
    }
    for(int i=0; i<fares.size(); i++) {
        cost[fares[i][0]][fares[i][1]] = fares[i][2];
        cost[fares[i][1]][fares[i][0]] = fares[i][2];
    }
    
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            for(int k=1; k<=n; k++) {
                if(cost[j][k] > cost[j][i] + cost[i][k])
                    cost[j][k] = cost[j][i] + cost[i][k];
            }
        }
    }
    for(int i=1; i<=n; i++) {
        answer = answer < cost[s][i] + cost[i][a] + cost[i][b] ?
            answer : cost[s][i] + cost[i][a] + cost[i][b];
    }
    
    return answer;
}

 

중요한 점은 왜 하필

for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            for(int k=1; k<=n; k++) {
                if(cost[j][k] > cost[j][i] + cost[i][k])
                    cost[j][k] = cost[j][i] + cost[i][k];
            }
        }
    }

이것인가?

i, j, k 순으로 for문을 돌면, 반드시 [j][k] : [j][i] + [i][k]

의 비교를 하는가? 

 

이렇게 해야, [j][k]를 n번에 한 번씩 갱신이 가능하다.

가령 총 6개의 정점에서, [5][4]를 [5][1]+[1][4]부터 [5][6]+[6][4]까지 비교를, 6회에 1번씩 가능하다.

이 때 [5][1]과 [1][4]의 최솟값 역시 이미 계산되어 있어야 한다.

6회에 1번씩 계산되므로, 이 계산이 안되는 사이에 [5][1] 역시 같이 갱신되어 더 작은값으로 바뀌어진다.

 

만일 [i][j] : [i][k] + [k][j]

로 비교를 할 경우,

한번에 [5][4]를 연속으로 내리 6회 비교를 한다.

따라서 [5][1]과 [1][4]의 최솟값이 갱신되어도 이것이 반영되지 않는다.

 

이로 인해 i, j, k 순으로 for문을 돌면, 반드시 [j][k] : [j][i] + [i][k] 순으로 계산을 한다.