백준 : 1507

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

1507번: 궁금한 민호

문제에 주어진 값들이 플로이드 와샬을 거친값이라는 것을 안다면 접근이 쉬워진다.

만약 주어진값이 와샬이 아니라면 최소의 간선으로 최소비용을 만들수 없으므로 -1을 출력한다.

주어진 값이 와샬이맞다면 현재 와샬로 그을수있는 모든 노드의 가중치를 긋고 

와샬 dp[i][j] == dp[i][k] +dp[k][j] 를 만족하는 i -- j 간선을 지워주면 된다.

이것이 왜가능한지를 생각해보면 와샬이전에 실제 노드에 대해서는 생각할 필요가없다.

와샬값으로 이전의 간선을 추리한다는것은 불가능하고 여기선 이 와샬필드를 가지고 최소로 만드는것에 주목해야한다.

그렇다면 와샬필드를가지고 N*(N-1) 개의 간선들을 이을수있다. 여기서 와샬을 만족한다면 모든필드에대해서

dp[i][j] <= dp[i][k] +dp[k][j] 를 만족한다  만약 두값이 같다면 i - j 간석을 지워도된다 왜냐면 i -k -j 로 가는 간선이 존재하기때문에 와샬을 바뀌지않는다

ps) 결론 : 와샬을 필드의 값들을 헤치지않으면서 간선들을 지울 수 있는것을 모두지우면 그것이 최소간선이다.

package algo;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class B1507 {
    static int N;
    static int edge[][];
    static int dp[][];
    static final int INF = 987654321;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        edge = new int[N][N];
        dp = new int[N][N];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                edge[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = edge[i][j];
            }
        }
 
        boolean isPossible = true;
 
        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 (dp[i][j] > dp[i][k] + dp[k][j]) {
                        isPossible = false;
                        break;
                    } else if(dp[i][j] == dp[i][k] + dp[k][j]){
                        edge[i][j] = 0;
                    }
 
                }
                if (!isPossible)
                    break;
            }
            if (!isPossible)
                break;
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(edge[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println();
        if (isPossible) {
            int sum = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (edge[i][j] == 0)
                        continue;
                    sum += edge[i][j];
                    edge[i][j] = 0;
                    edge[j][i] = 0;
                }
            }
            System.out.println(sum);
        } else {
            System.out.println(-1);
        }
 
    }
}