BOJ 31815 - Construct a Graph 링크
(2024.05.15 기준 P5)

문제

 $N \times N$ 크기의 행렬 $D$가 주어진다.
모든 정점 쌍 $(u, v)$에 대해 $u$와 $v$의 최단 경로는 $D_{u,v}$이어야 하며, 모든 간선의 가중치의 합은 가능한 최소여야 하는, 무방향 연결 그래프를 구성해 출력

알고리즘

플로이드 워셜의 성질을 이용

풀이

플로이드 워셜에서 거리를 갱신할 때 조건은 $D_{i, j} > D_{i, k} + D_{k, j}$이다. 이는 $i \rightarrow j$보단 $i \rightarrow k \rightarrow j$ 경로로 경유해서 가는 것이 더 빠르다는 소리다.

만약 $D_{i, j} = D_{i, k} + D_{k, j}$라면? $i \rightarrow j$ 경로와 $i \rightarrow k \rightarrow j$ 경로의 길이는 같다는 뜻이다. 이는 즉, 간선 $(i, k)$와 간선 $(k, j)$만 있으면, 간선 $(i, j)$의 역할이 없어진다는 말이다. 이를 이용하자.

주어지는 행렬 $D$에 대해 플로이드 워셜처럼 경유지 $k$와 두 정점 $i$, $j$에 대해 검사해보자. $(i \ne j \ne k)$
$D_{i, j} > D_{i, k} + D_{k, j}$를 만족한다면? 주어진 행렬 $D$는 최단 경로를 나타내는 행렬이 아니게 된다. 그러므로 $-1$을 출력하자.
$D_{i, j} = D_{i, k} + D_{k, j}$을 만족한다면? 간선 $(i, j)$는 필요 없다.

위와 같이 $O(N^3)$로 검사해서 필요한 간선만 출력하면 된다.

코드

• C++

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

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    int D[N][N]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> D[i][j];

    // 일단 처음엔 모든 간선이 필요하다고 가정
    bool need[N][N]; memset(need, false, sizeof(need));
    int n = 0;
    for (int i = 0; i < N - 1; i++) for (int j = i + 1; j < N; j++){
        need[i][j] = true;
        ++n;
    }

    for (int k = 0; k < N; k++) for (int i = 0; i < N; i++){
        if (i == k) continue;
        for (int j = 0; j < N; j++){
            if (i == j || j == k) continue;

            // 거리를 갱신할 수 있다면, 주어진 거리는 성립할 수 없다.
            if (D[i][j] > D[i][k] + D[k][j]){
                cout << -1;
                return 0;
            }

            // 간선 (i, j)는 간선 (i, k)와 간선 (k, j)가 있으면 필요 없어진다.
            if (D[i][j] == D[i][k] + D[k][j]) if (need[i][j]){
                need[i][j] = false;
                --n;
            }
        }
    }

    cout << n << '\n';
    for (int i = 0; i < N - 1; i++) for (int j = i + 1; j < N; j++)
        if (need[i][j]){
            cout << i + 1 << ' ' << j + 1 << ' ' << D[i][j] << '\n';
        }
}

• Python (PyPy3)

import sys; input = sys.stdin.readline

N = int(input())
D = [list(map(int, input().split())) for _ in range(N)]

# 일단 처음엔 모든 간선이 필요하다고 가정
need = [[False] * N for _ in range(N)]
n = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        need[i][j] = True
        n += 1

for k in range(N):
    for i in range(N):
        if i == k:
            continue
        for j in range(N):
            if i == j or j == k:
                continue

            # 거리를 갱신할 수 있다면, 주어진 거리는 성립할 수 없다.
            if D[i][j] > D[i][k] + D[k][j]:
                print(-1)
                exit()

            # 간선 (i, j)는 간선 (i, k)와 간선 (k, j)가 있으면 필요 없어진다.
            if D[i][j] == D[i][k] + D[k][j]:
                if need[i][j]:
                    need[i][j] = False
                    n -= 1

print(n)
for i in range(N - 1):
    for j in range(i + 1, N):
        if need[i][j]:
            print(i + 1, j + 1, D[i][j])