백준 1956 - 운동

문제

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

리뷰

주어진 문제에서는 최소 비용 사이클을 구해야 한다. 따라서 모든 경로에 대한
최소 비용을 구하는 플로이드-워셜을 활용할 수 있었다.

전형적인 플로이드 워셜 로직에서 i==j 인 경우(사이클인 경우)에 현재까지의
사이클 최소 비용인 minCost 를 갱신하는 방식으로 문제를 풀이하였다.

로직의 시간복잡도에서 가장 큰 비중을 차지하는 플로이드-워셜의 경우 $O(V^3)$의
시간복잡도로 수렴하므로 $V$의 최대값인 400의 경우에도 연산이 6400만정도라
시간 제한인 2초를 무난히 통과할 수 있었다.

문제를 풀며 가장 유의해야할 부분은 플로이드-워셜을 위한 2차원 배열 map의
초기값을 어떤 것으로 설정할 지에 관한 부분이었다. 필자는 안전하게 Integer.MAX_VALUE로
설정한 후 플로이드-워셜 로직내에서 오버플로우가 나지 않게 별도의 조건문을 추가하여 처리했다.

코드

import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

public class Main {
    static int V, E;

    static int[][] map;
    static int minCost = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(in.nextLine());

        V = parseInt(st.nextToken());
        E = parseInt(st.nextToken());

        map = new int[V + 1][V + 1];
        for (int i = 1; i < map.length; i++)
            Arrays.fill(map[i], Integer.MAX_VALUE);

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(in.nextLine());

            int u = parseInt(st.nextToken());
            int v = parseInt(st.nextToken());
            int c = parseInt(st.nextToken());

            map[u][v] = c;
        }

        floyd();

        System.out.println(minCost == Integer.MAX_VALUE ? -1 : minCost);
        in.close();
    }

    static void floyd() { // O(V^3)
        for (int k = 1; k <= V; k++)
            for (int i = 1; i <= V; i++)
                for (int j = 1; j <= V; j++) {
                    if (map[i][k] == Integer.MAX_VALUE || map[k][j] == Integer.MAX_VALUE)
                        continue;

                    map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);

                    if (i == j)
                        minCost = Math.min(minCost, map[i][j]);

                }
    }
}

결과