[BOJ_11265] 끝나지 않는 파티

설명

 

가중치가 부여된 그래프 상에서 단방향 일 때 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘인 플로이드 와샬 알고리즘을 사용하면 거리를 쉽게 구할 수 있습니다.

 

먼저 2차원 배열을 초기화 합니다. 각 배열의 정점에서 다른 모든 정점으로의 직접적으로 도착하는 이동거리를 찾습니다.

 

그 후, 알고리즘 상세를 살펴 보자면 X -> Y 까지의 최소 비용을 구한 것arr[X][Y]으로 이러한 방식으로 비용을 찾아나가는데. 예시로 X -> Y -> Z 가 만일, X->Z 최소 이동거리라면 arr[X][Y] + arr[Y][Z]를 구합니다.

 

즉, for문을 보면 알겠지만 출발지 i , 목적지 j, 중간 지점을 k로 둡니다. 이미 i -> j가 최소인 경우에는 탐색을 하지 않겠지만 만일, k를 거쳐서 갈 때 최소가 되는 곳이 생긴다면 이를 이용해서 초기화를 합니다.

 

그러면 이를 반복하면 최소의 거리 값으로 i to j 의 거리가 나오게 됩니다. 허나, 주의 할 점이 있습니다. 만일, i,j,k 순으로 for문을 나열하고 식은 그대로 쓰면 어떻게 될까요? 

 

그러면 오류가 나는데요. 이는 k 번 정점이 중간 목적지가 되어야 하는데 k번 까지 거쳐들어오는 정점까지의 최단 거리가 먼저 초기화가 되어야 최단 거리를 구할 수 있습니다. 따라서, arr[i][k]와 같이 가장 초기에 초기화가 진행 된 정점을 바탕으로 연결하게 됩니다.

 

이를 고려해서 코드를 작성하면 됩니다.

 

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int M = scanner.nextInt();
        int[][] time = new int[N+1][N+1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                time[i][j] = scanner.nextInt();
            }
        }

        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (time[i][j] > time[i][k] + time[k][j]) {
                        time[i][j] = time[i][k] + time[k][j];
                    }
                }
            }
        }

        for (int m = 0; m < M; m++) {
            int A = scanner.nextInt();
            int B = scanner.nextInt();
            int C = scanner.nextInt();
            if (time[A][B] <= C) {
                System.out.println("Enjoy other party");
            } else {
                System.out.println("Stay here");
            }
        }
    }
}

11265번: 끝나지 않는 파티