문제

문제 링크

이미 최단 경로를 구한 그래프에서 어떠한 그래프에서 시작하는지를 알아보는 문제다.

보통 플로이드 워셜 문제에서는 노드들간의 거리를 주고
각 노드들간의 최단 거리를 구하는것이 일반적인데

이 문제는 정확히 반대다.

고민을 많이 했다.
노드들간의 1-2-3처럼 2를 한번 경유하는 경우는 쉽게 찾을 수 있을거같았는데
1-2-3-4가 1-4에 최단 거리라면 어떻게 구해야할지 막막했다.
근데 생각을 좀 더 해보니 1-2-3-4가 최단이라는 말은 1-2-4,1-3-4도 최단이라는 소리다.(다 연결되어있기 때문이다.)

그러면 문제가 해결가능했다.

예제의 정답은 55인데 그림으로 그려보면 다음과 같다.

그래프를 따라 원래 상태도 유추할수 있었다.
그러면 최단 경로가 아닌 경우를 체크해서 나중에 최단 경로만 더해주면 해결되었다.

불가능한 경우를 -1 로 반환하라는데 문제가 좀 불친절한건지
무슨 경우인지가 쉽게 떠오르지 않았다.

그래서 모든 노드가 연결되지 않는 경우인가 싶어서 union-find로 시도해보렸는데 문제에서 모든 노드가 연결되어있다고 했다.
못해먹었겠어서 질문을 찾아보니,
불가능한 경우는 결국 해당 그래프가 처음부터 최단 거리가 아닌 경우였다.

반대로 생각해보는것도 쉽지 않았는데 불가능한 경우에 대한 설명이 없어서 너무 당황스러웠던 문제다.

code

/**
 * 백준 1507
 * 플로이드 워셜
*/
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

int n;
int graph[20][20];
bool check[20][20]={false};

int prim(void){
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i==j || i==k || k==j || i>j) continue;
                if(graph[i][j]==(graph[i][k]+graph[k][j])){
                    check[i][j]=true;
                }
                else if(graph[i][j]>(graph[i][k]+graph[k][j])){
                    return -1;
                }
            }
        }
    }

    int ret=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i<j && !check[i][j]){
                //cout<<"check : "<<i<<","<<j<<endl;
                ret+=graph[i][j];
            }
        }
    }
    return ret;
}

int main(void){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&graph[i][j]);
        }
    }
    
    int ans = prim();
    cout<<ans<<endl;
}