백준 11265 끝나지 않는 파티 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/11265

풀이는 다음과 같다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 새로운 파티장과 기존의 모든 파티장이 직접적으로 연결이 될 수 있는 도로들을 만들었다.
        // 이때 만들어진 도로들은 사용자들의 편의를 위해 일방통행

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st1.nextToken());
        int M = Integer.parseInt(st1.nextToken());

        int[][] floyd = new int[N][N];
        for(int i = 0 ; i < N ; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < N ; j++) {
                floyd[i][j] = Integer.parseInt(st2.nextToken());
            }
        }

        //초깃값 완성

        for(int k = 0 ; k < N ; k++) {
            for(int i = 0 ; i < N ; i++) {
                if(k == i) continue;
                for(int j = 0 ; j < N ; j++){
                    if(i == j || j == k) continue;
                    if(floyd[i][j] > floyd[i][k] + floyd[k][j]) floyd[i][j] = floyd[i][k] + floyd[k][j];

                }
            }
        }

        //플로이드, 와샬 알고리즘으로 floyd[i][j] 는 i에서 j까지의 최솟값으로 바뀜.

        for(int i = 0 ; i < M ; i++) {
            StringTokenizer st3 = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st3.nextToken()); //현재 위치
            int B = Integer.parseInt(st3.nextToken()); //가고싶은 위치
            int C = Integer.parseInt(st3.nextToken()); //주어진 시간

            if(floyd[A-1][B-1] > C) { //최솟값이 주어진 시간보다 크다면 못가
                bw.write("Stay here\n");
            }
            else {
                bw.write("Enjoy other party\n");
            }
        }


        bw.flush();
        bw.close();
        
    }
    
}

더 설명할 내용은,
플로이드 와샬 알고리즘이다.

쉽게말해,
플로이드 워셜 로직 = a->c로 가는 값보다 b를 거쳐 a->b + b->c 값이 더 작다면 작은 값을 택하는 알고리즘.

바로 위의 로직은 하나의 노드를 거쳐 가지만(a->b->c),

해당 로직이 반복되면 수많은 노드를 거쳐도 (a->b->c->d->e)
시작노드와 도착노드만 남게 된다 (a->e)

간단한 예시.

행렬의 의미는, 행에서 열의 노드로 갈때의 거리라고 하자. 거리가 없으면
다익스트라처럼 Integer.MAX_VALUE를 넣었다고 하자.

무한 2 10
1 무한 5
2 2 무한

해당 행렬에서,
1 -> 3을 바로가는 값은 1행 3열이므로, 10이다.
하지만,
1 -> 2 + 2 -> 3을 통해 2를 거쳐가는 값은 1행 2열 + 2행 3열이므로, 7이다.
7이 더 작으므로 행렬이

무한 2 7
1 무한 5
2 2 무한

이런 방식으로 바뀌는것이다.

PS.
플로이드 워셜 기억할 내용 : k, i, j순서 + 값 같을때 continue;