[ BOJ 백준 1507번 - 궁금한 민호 ] 해설 및 코드

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

목적

모든 쌍의 도시 사이의 최소 이동 시간이 주어졌을 때, 이 나라에 존재할 수 있는 도로의 개수의 최솟값과 그 때, 모든 도로의 시간의 합을 구하자.

 

접근법

1. 플로이드 와샬 알고리즘으로 a에서 b로의 최단 거리를 구한 결과(인접행렬)가 주어졌을 때, 이를 알고리즘 수행 이전으로 돌려보라는 문제이다. 단 도로의 개수를 최소로 하기 위해 불필요한 도로는 모두 제거해야 한다.

2. 인접행렬에서 지울 수 있는 도로에 해당하는 요소를 INF값으로 할당한다. 도로 s[i][j]는 s[i][k] + s[k][j] == s[i][j]를 만족하는 k가 존재한다면 지워나간다. 

3. 초기 상태의 인접 행렬에서 시간의 합을 구하고, 재차 플로이드 와샬 알고리즘을 적용하여 모든 노드간의 최단 거리를 구한 뒤 원래 인접행렬과 비교한다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
 
const int INF=2e6;
int n,s[21][21],t[21][21];
 
int sol(){
    f(i,1,n)f(j,i+1,n)f(k,1,n)if(k!=i&&k!=j){
        int tmp=s[i][k]+s[k][j];
        if(s[i][j]==tmp)t[i][j]=t[j][i]=INF;
    }
    int ret=0;
    f(i,1,n)f(j,i+1,n)if(t[i][j]!=INF)ret+=t[i][j];
    
    f(k,1,n)f(i,1,n)f(j,i+1,n)if(t[i][k]!=INF&&t[k][j]!=INF){
        int tmp=t[i][k]+t[k][j];
        if(t[i][j]>tmp)t[i][j]=t[j][i]=tmp;
    }
    
    f(i,1,n)f(j,i+1,n)if(s[i][j]!=t[i][j])return -1;
    return ret;
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    f(i,1,n)f(j,1,n){
        cin>>s[i][j];
        t[i][j]=s[i][j];
    }
    cout<<sol();
    
    return 0;
}
 

 

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

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