[BOJ1507] 궁금한 민호 (플로이드 워셜)

 

 

---

문제 링크 

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

1507번: 궁금한 민호

 

문제 풀이

- 직접 풀이하지 못하여 아래 기술 블로그 참고 후 풀이

- 최소라는 단어에 매몰되어 이진 탐색 후 완전탐색을 해야 하나하고 삽질함 (당연히 시간초과)

 

https://steady-coding.tistory.com/105

[BOJ] 백준 1507번 : 궁금한 민호 (JAVA)

 

플로이드 워셜 알고리즘의 경우 각 노드를 시작점으로 했을 때 다른 노드에 갈 수 있는 최단 거리를 구하는 알고리즘이다.

 

점화식

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

dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j])

i -> j로 바로가는 최단 거리와 k를 거쳐 i -> j로 가는 최단거리(dist[i][k] + dist[k][j]) 중 더 작은 값을 구하게 된다. 

 

모든 쌍의 도시 사이의 최소 이동 시간이 주어졌을 때

1) 플로이드 워셜 알고리즘을 한번 더 돌렸을 때 최단 거리 갱신되는 경우 모순이기 때문에 -1 출력하고 종료한다.

2) dist[i][j] == dist[i][k] + dist[k][j] 일 때, 즉 i -> j 바로가나 k를 거쳐서 가나 값이 동일한 경우 INF로 간선을 없앤 표시를 해준다

입력예제 1에 대한 플로이드 워셜과 추가 로직 실행했을 때 결과

 

아래 예시와 같이 좌변에 (1,3)으로 바로 갈때 최소 이동 시간이 15인데,

k = 2를 거쳐 간 경우에도 15이므로 (1,3) 간선을 하나 제거한다 ( k를 거쳐가는 간선을 건드릴 수는 없으니)

 

3) 최종적으로 2)을 통해 도로의 개수를 최소로 줄인 후 간선에 대한(중복 제외) 합계를 구해 출력 한다

 

 

제출 코드

import java.util.*;
import java.io.*;

public class Main {
    
    static int N;

    static int[][] floyd, arr;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        floyd = new int[N + 1][N + 1];
        arr = new int[N + 1][N + 1];

        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= N; j++) {
                floyd[i][j] = Integer.parseInt(st.nextToken());
                arr[i][j] = floyd[i][j];
            }
        }
    }

    static void pro() {
        boolean isValid = true;
        
        Loop :
        for(int k = 1; k <= N; k++) {
            for(int i = 1; i <= N; i++) {
                for(int j = 1; j <= N; j++) {
                    if(i == j || i == k || k == j) continue;

                    if(floyd[i][j] > floyd[i][k] + floyd[k][j]) {
                        isValid = false;
                        break Loop;
                    }

                    if(floyd[i][j] == floyd[i][k] + floyd[k][j]) {
                        arr[i][j] = Integer.MAX_VALUE;
                    }
                }
            }
        }

        int ans = 0;
        if(isValid) {
            boolean[][] checked = new boolean[N + 1][N + 1];
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (i == j) continue;
                    if (arr[i][j] != Integer.MAX_VALUE && !checked[i][j]) {
                        ans += arr[i][j];
                        checked[i][j] = checked[j][i] = true;
                    }
                }
            }
        }

        System.out.println(ans == 0 ? -1 : ans);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}