백준 21278 호석이 두 마리 치킨 자바

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

풀이는 다음과 같다.

import java.io.*;
import java.util.*;
public class Main {
    static int[][] floyd;
    static int N, M;
    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());
        N = Integer.parseInt(st1.nextToken());
        M = Integer.parseInt(st1.nextToken());

        floyd = new int[N][N];
        
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                floyd[i][j] = 101; //점의 최대 개수는 100개이므로, 점과 점은 아무리 멀어도 거리 99가 최대임.
                //즉, 거리 101로 해주는 것은 다익스트라의 Integer.MAX_VALUE와 같음.
            }
        }
        //존재하는 길이 없다. 를 101 로 표현.
        //있으면, 거리는 전부 1이니 해당 값 넣기
        
        for(int i = 0 ; i < M ; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st2.nextToken());
            int b = Integer.parseInt(st2.nextToken());
            floyd[a-1][b-1] = 1;
            floyd[b-1][a-1] = 1;
        }
        //초깃값.

        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                if(i == j) continue;
                for(int k = 0 ; k < N ; k++) {
                    if(i == k || j == k) continue;
                    
                    if(floyd[j][k] > floyd[j][i] + floyd[i][k]) floyd[j][k] = floyd[j][i] + floyd[i][k];
                    
                }
            }
        }
        
        //플로이드 워셜로 각 점에서 각 점까지의 거리의 최솟값 다 채운 후
        //플로이드 워셜 로직 = a->c로 가는 값보다 b를 거쳐 a->b + b->c 값이 더 작다면 작은 값을 택하는 알고리즘.
        
        int min = Integer.MAX_VALUE;
        int n1 = 0;
        int n2 = 0;

        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                if(i == j) continue;
                //두 점을 고른다. (1, 2부터 N-1, N까지)

                int now = sum(i, j);
                //고른 두 점을 기준으로 각각의 점의 거리의 최솟값을 더해나간다.
                //1, 2를 골랐으면
                //sum(1, 2) = 그 둘(1, 2)에서 3까지의 거리의 최솟값 + ... + 그 둘(1, 2)에서 N 까지의 거리의 최솟값

                if(min > now) {
                    n1 = i+1;
                    n2 = j+1;
                    min = now;
                }
                //해당 값이 최솟값이 된다면 두 점을 기록해놓는다.

            }
        }

        //기록한 두 점과 최솟값을 출력한다.
        bw.write(String.valueOf(n1) + " " + String.valueOf(n2) + " " + String.valueOf(min*2)); //min*2는 왕복이라서.
        bw.flush();
        bw.close();


    }

    static int sum(int n1, int n2) {
        int sum = 0;
        for(int i = 0 ; i < N ; i++) {
            if(i == n1 || i == n2) continue;
            sum += Math.min(floyd[n1][i], floyd[n2][i]);
        }

        return sum;
    }


}

처음엔, 오우~ 최솟값 구하는거구만? 하고
다익스트라를 사용했는데 시간초과가 뜨더라.
그래서 찾아보니, 다익스트라 말고
플로이드 워셜 알고리즘 사용한다더라.
근데, 플로이드 워셜 알고리즘은 사용해본적이 없어
공부하고 배우고 풀었다.
생각보다 어려운 알고리즘은 아니다.

쉽게말해,
플로이드 워셜 로직 = 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;
그리고
https://www.youtube.com/watch?v=9574GHxCbKc&t=532s
해당 링크를 보고 플로이드 워셜 알고리즘을 공부했다.