[ BOJ 백준 1719번 - 택배 ] 해설 및 코드

https://www.acmicpc.net/problem/1719

 

목적

모든 정점쌍 간의 최단거리를 구하고, 거쳐가야 할 정점을 구하자.

 

접근법

1. 문제 분류는 다익스트라이지만, 모든 두 정점간의 최단 거리를 구해야하므로, 플로이드 와샬 알고리즘이 더 적합하다고 본다.

2. 플로이드 와샬 알고리즘에 의해 K 정점에 따라 최단 거리가 갱신될 때, 거쳐가야하는 첫번째 노드를 갱신해준다.

 

#include<iostream>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m,g[201][201],ans[201][201],INF=200001;
    cin>>n>>m;
    f(i,1,n)f(j,1,n)g[i][j]=INF;
    f(i,1,n)g[i][i]=0;
    while(m--){
        int a,b,c;cin>>a>>b>>c;
        g[a][b]=g[b][a]=c;
        ans[a][b]=b;
        ans[b][a]=a;
    }
    
    f(k,1,n)f(i,1,n)f(j,1,n)if(g[i][j]>g[i][k]+g[k][j]){
        g[i][j]=g[i][k]+g[k][j];
        ans[i][j]=ans[i][k];
    }
    
    f(i,1,n){
        f(j,1,n){
            if(i==j)cout<<'-';
            else cout<<ans[i][j];
            cout<<' ';
        }
        cout<<'\n';
    }
    
    return 0;
}

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.