[랜덤 마라톤] 끝나지 않는 파티(11265)

1. 문제 풀이 아이디어

• 플로이드 워셜 알고리즘을 사용하면 문제를 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int n = Integer.parseInt(stringTokenizer.nextToken());
        int m = Integer.parseInt(stringTokenizer.nextToken());
        int[][] t = new int[n][n];
        for (int i = 0; i < n; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for (int j = 0; j < n; j++) {
                t[i][j] = Integer.parseInt(stringTokenizer.nextToken());
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    int tt = t[j][i] + t[i][k];
                    t[j][k] = Math.min(t[j][k], tt);
                }
            }
        }

        for (int i = 0; i < m; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int a = Integer.parseInt(stringTokenizer.nextToken());
            int b = Integer.parseInt(stringTokenizer.nextToken());
            int c = Integer.parseInt(stringTokenizer.nextToken());
            stringBuilder.append(t[a - 1][b - 1] > c ? "Stay here" : "Enjoy other party").append('\n');
        }
        System.out.print(stringBuilder);
        bufferedReader.close();
    }
}

3. 정리

• 각 노드 간의 거리를 배열 t에 저장한다.

• 플로이드-워셜 알고리즘을 사용하여 j에서 k로 가는 최단 거리를 계산해 다시 t 배열에 저장한다.

• 이 과정에서 중간 노드(i)가 상위에 위치해야 한다.

• 이후 입력으로 주어진 a, b, c 값에 따라 결과를 출력하여 문제를 해결한다.