백준 23286 - 허들 넘기

문제

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

리뷰

플로이드-워셜 알고리즘을 이용하여 풀이할 수 있는 문제였다. 주어진 문제의 조건중
가장 높은 허들 높이의 최솟값이라는 조건을 잘 이해하지 못해 상당히 애를 먹었다.
결론적으로 그냥 말그대로를 플로이드-워셜내 값 갱신 조건으로 구현하면 되었다.

로직의 시간복잡도는 가장 연산이 많이 소요되는 플로이드-워셜 부분만 고려하였을 때
$O(N^3)$이므로 $N$이 300일때도 2700만 가량이라 2초의 제한 조건을 무난히
통과할 수 있었다.

답을 append 하는 과정에서 -1의 경우 개행문자가 제대로 문자열에 제대로 포함되지
않는 방식으로 ?연산자를 활용하는 바람에 애먼 데서 시간을 소비했다. 코드를 세심히
살피는 태도를 다시금 상기시키게 된 문제였다.

코드

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

import static java.lang.Integer.MAX_VALUE;
import static java.lang.Integer.parseInt;

public class Main {
    static int[][] map;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(in.nextLine());
        int N = parseInt(st.nextToken());
        int M = parseInt(st.nextToken());
        int T = parseInt(st.nextToken());

        map = new int[N + 1][N + 1];

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

        while (M-- > 0) {
            st = new StringTokenizer(in.nextLine());
            int u = parseInt(st.nextToken());
            int v = parseInt(st.nextToken());
            int h = parseInt(st.nextToken());

            map[u][v] = h;
        }

        floyd();
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            st = new StringTokenizer(in.nextLine());
            int start = parseInt(st.nextToken());
            int end = parseInt(st.nextToken());

            sb.append(map[start][end] == MAX_VALUE ? -1 : map[start][end]);
            sb.append("\n");
        }

        System.out.print(sb);
        in.close();
    }


    static void floyd() {
        for (int k = 1; k < map.length; k++)
            for (int i = 1; i < map.length; i++)
                for (int j = 1; j < map.length; j++) {
                    map[i][j] = Math.min(map[i][j], Math.max(map[i][k], map[k][j]));
                }
    }
}

결과