[C++] 백준 - 1719 : 택배

문제 링크

1719번: 택배

 

 

풀이 )

  플로이드 알고리즘을 이용해서 풀었다.

 

  adj배열에는 소요시간을, route배열에는 이전 방문 집하장을 각각 저장했다.

  입력을 받은 후, 자신으로 가는 소요시간과 입력 이외의 모든 소요시간을 INF, 즉 설정해놓은 최댓값으로 초기화시키고, 거치는 집하장이 없다고 초기화한다.

 

  1번 집하장부터 순서대로 경로에 추가하면서, 시작지점에서 1번 집하장을 들려서 목적지에 도착하는 것과 현재의 소요시간을 비교하여 들려서 도착하는 값이 더 작은 경우 해당 adj, route 배열에 대해서 업데이트해준다.

 

  단 이럴 경우 문제에서 요구하는 가장 먼저 거쳐야 하는 집하장이 아닌 도착 직전에 거친 집하장이 route 배열에 저장되기 때문에 출력 이전에 경로를 되돌아가면서 처음 거치는 집하장을 찾는다.

#include <iostream>

#define INF 1e9;

using namespace std;

int adj[201][201];
int route[201][201];

int main(void){
    int n, m;
    cin >> n >> m;
    while(m--){
        int v1, v2, weight;
        cin >> v1 >> v2 >> weight;
        adj[v1][v2] = weight;
        adj[v2][v1] = weight;
    }

    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            if(i == j)
                continue;
            route[i][j] = j;
            if(!adj[i][j])
                adj[i][j] = INF;
        }
    }

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

    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            if(i == j)
                continue;
            if(route[i][j] == j)
                continue;
                
            int cur = j;
            while(route[i][cur] != cur)
                cur = route[i][cur];
            route[i][j] = cur;
        }
    }

    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            if(i == j)
                cout << '-';
            else
                cout << route[i][j];

            if(j == n)
                cout << '\n';
            else
                cout << ' ';
        }
    }
}

 

주의 )

  출력하는 경로표는 '가장 먼저 거쳐야 하는 집하장'을 나타낸 것이다.