BOJ 1507 궁금한 민호

문제

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

어떤 그래프에서의 임의의 두 정점 간의 최단거리가 모두 주어졌을 때, 조건을 만족하며 간선의 개수를 최소화할 수 있는 그래프를 찾는 문제이다.

 

풀이

기본적인 풀이는 $N^2$ 개의 간선을 모두 생성한 후, 필요 없는 간선을 하나씩 지워 가며 문제를 해결한다.

그렇다면 과연, 필요 없는 정점을 어떻게 구할 수 있을까?

 

u->v 의 간선을 삭제하기 위해서는 u->w->v 의 경로와의 거리와 비교해 볼 필요가 있다.

1) adj[u][v]<adj[u][w]+adj[w][v]

u->v 의 간선을 삭제해서는 안된다. u->v 의 최단거리는 다른 경유점을 거쳐 가면 안됀다는 뜻이기 떄문이다.

2) adj[u][v]==adj[u][w]+adj[w][v]

u->v 의 간선을 굳이 놔둘 필요가 없다. u->v의 간선을 놔두고 u->w, w->v의 경로를 택해 이동하면 된다.

3) adj[u][v]>adj[u][w]+adj[w][v]

모순이다. u->v 의 최단거리가 adj[u][v]가 아닌, adj[u][w]+adj[w][v] 로 대체 가능하므로, 최단거리가 될 수 없다.

 

이는 플로이드-워셜 알고리즘의 작동 방식과 매우 유사하다.

기본적으로 경로 u->v의 최단거리를 구하기 위하여 임의의 경유점을 설정한 후, 그 점을 지나는 경로를 찾는 아이디어 자체를 플로이드 워셜 알고리즘에서 가져왔다고 생각해도 무방하기 때문이다.

 

시간 복잡도 : $O(N^3)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 20;

int n, adj[MAXN+10][MAXN+10], ans;

int main()
{
    int i, j, k;

    scanf("%d", &n);
    for(i=1; i<=n; i++) for(j=1; j<=n; j++) scanf("%d", &adj[i][j]);

    for(i=1; i<=n; i++) for(j=i+1; j<=n; j++)
    {
        bool flag=true;
        for(k=1; k<=n; k++)
        {
            if(k==i || k==j) continue;
            if(adj[i][j]==adj[i][k]+adj[k][j]) flag=false;
            else if(adj[i][j]>adj[i][k]+adj[k][j]) return !printf("-1");
        }
        if(flag) ans+=adj[i][j];
    }
    printf("%d", ans);
}