백준 11265 - 끝나지 않는 파티

문제

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

리뷰

플로이드-워셜로 풀이할 수 있는 간단한 문제였다.

손님이 최단 경로로 이동하였을때 파티가 준비되는 시간(C)안에 도달할 수 있는지
구하는 것이 문제의 요구사항이다.

따라서 플로이드-워셜을 이용해 모든 정점간의 최단 경로 비용을 구한뒤 이를
바탕으로 M 개의 쿼리에 답하는 식으로 로직을 구성했다.

로직의 시간복잡도는 플로이드-워셜의 $O(N^3)$으로 수렴하고 이는 $N=500$인
최악의 경우에도 제한 조건 2초를 무난히 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

import static java.lang.Integer.*;

public class Main {
    static String[] answer = {"Enjoy other party", "Stay here"};
    static int N;
    static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = parseInt(st.nextToken());
        int M = parseInt(st.nextToken());

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

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 1; j <= N; j++) {
                map[i][j] = parseInt(st.nextToken());
            }
        }

        floyd();

        int A, B, C;
        StringBuilder sb = new StringBuilder();
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            A = parseInt(st.nextToken());
            B = parseInt(st.nextToken());
            C = parseInt(st.nextToken());

            String ans = map[A][B] <= C ? answer[0] : answer[1];
            sb.append(ans).append("\n");
        }

        System.out.println(sb);
        br.close();
    }

    static void floyd() {
        for (int k = 1; k <= N; k++)
            for (int i = 1; i <= N; i++)
                for (int j = 1; j <= N; j++) {
                    if (map[i][k] == MAX_VALUE || map[k][j] == MAX_VALUE)
                        continue;

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

}

결과