[JAVA] 백준 1507번 【G2.궁금한 민호】

문제

1507번: 궁금한 민호

 

풀이

1️⃣ 플로이드 알고리즘을 이용한 풀이

💡 참고한 Idea

먼저 입력으로 주어지는 비용 그래프가 플로이드 알고리즘을 이미 한번 거친 비용 그래프라고 생각해야한다.

그리고나서, 이 그래프를 다시 분해를 해야하는데 어떻게 분해할 수 있을까?

플로이드 알고리즘의 경우

costs[u][v] = Math.min(costs[u][v], costs[u][m] + costs[m][v]);​

위와 같이 u에서 v로 가는 비용보다, u에서 m으로 간다음 m에서 v를 거쳐서 가는 비용이 싼 경우 업데이트를 하는 방식이다.

따라서,

입력받은 비용 그래프에서

costs[u][v] == costs[u][m] + costs[m][v]

위와 같은 조건을 만족하는 u v가 존재할 때

u와 v는 플로이드 알고리즘에 의해 연결된 간선이고 실제로는 존재하지 않는 간선으로 간주할 수 있다.

(단, u와 v, m은 서로 다른 위치여야한다.)

따라서 위 조건을 만족하면 costs[u][v] = INF 을 입력하여 간선을 제거하는 작업이 필요하다.

그렇게 다시 분해한 그래프를 통해, 플로이드 알고리즘으로 최소 비용을 다시 구해보고

다시 구한 최소 비용 배열이 처음에 입력받은 비용 배열과 일치하는지 안하는지 체크하면된다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        final int MAX = 250000;
        int[][] g = new int[N][N];
        for (int u = 0; u < N; u++) {
            String[] input = br.readLine().split(" ");
            for (int v = 0; v < N; v++) {
                g[u][v] = Integer.parseInt(input[v]);
            }
        }

        int[][] costs = deepCopy(g);

        for (int m = 0; m < N; m++) {
            for (int u = 0; u < N; u++) {
                for (int v = 0; v < N; v++) {
                    if (costs[u][v] == costs[u][m] + costs[m][v] && (u != v && v != m && u != m)) {
                        costs[u][v] = MAX;
                        costs[v][u] = MAX;
                    }
                }
            }
        }

        int ans = 0;
        for (int r = 0; r < N; r++) {
            for (int c = r + 1; c < N; c++) {
                if (costs[r][c] != MAX) {
                    ans += costs[r][c];
                }
            }
        }

        for (int m = 0; m < N; m++) {
            for (int u = 0; u < N; u++) {
                for (int v = 0; v < N; v++) {
                    costs[u][v] = Math.min(costs[u][v], costs[u][m] + costs[m][v]);
                }
            }
        }

        if (isSame(costs, g)) {
            System.out.println(ans);
        } else {
            System.out.println(-1);
        }


    }

    private static boolean isSame(int[][] costs, int[][] g) {
        int N = g.length;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (costs[r][c] != g[r][c]) {
                    return false;
                }
            }
        }
        return true;
    }

    private static int[][] deepCopy(int[][] g) {
        int N = g.length;
        int[][] result = new int[N][N];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                result[r][c] = g[r][c];
            }
        }
        return result;
    }
}

결과