[백준]1238: 파티 - JAVA

[백준]1238: 파티

www.acmicpc.net/problem/1238

1238번: 파티

풀이

처음에는 다익스트라 알고리즘을 사용하여 풀려고 하였다. X에서 모든 마을 까지의 거리를 구하는 방법은 어렵지 않았으나 모든 마을에서 X까지 거리를 구하는 방법이 어려웠다. 결국 각각의 마을에서 X까지 가는 모든 최단거리를 구하고 그 중에 X로 가는 거리만 뽑아내려고 하였다. 그런데 생각해보니 이건 모든 노드에서 모든 노드까지의 최단거리를 구하는 것과 다름이 없었고 즉 플로이드 와샬 알고리즘을 사용하면 되겠다는 생각이 들었다.

 

그래서 플로이드-와샬 알고리즘을 사용했다. 간단히 구현할 수 있었다. 다익스트라를 사용한 풀이법을 찾아보니 간선을 모두 뒤집어서 계산을 하면 모든 마을에서 X까지의 거리를 구할 수 있었다. 이건 정말 생각하지도 못한 방법이었다. 시간복잡도도 더 효율적인 방법이었다. 다음에는 다익스트라를 사용해 구현해 보아야 겠다. 

 

코드

import java.util.*;
 
public class Main {    
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        int m = scan.nextInt();
        int x = scan.nextInt();
        
        int[][] node = new int[n + 1][n + 1];
        for(int i = 1; i < n + 1; i++) {
            for(int j = 1; j < n + 1; j++) {
                node[i][j] = 10000001;
            }
            node[i][i] = 0;
        }
        
        for(int i = 0; i < m; i++) {
            int start = scan.nextInt();
            int end = scan.nextInt();
            int cost = scan.nextInt();
            if(node[start][end] > cost) node[start][end] = cost;
        }
        
        for(int k = 1; k < n + 1; k++) {
            for(int i = 1; i < n + 1; i++) {
                for(int j = 1; j < n + 1; j++) {
                    if(node[i][j] > node[i][k] + node[k][j])
                        node[i][j] = node[i][k] + node[k][j];
                }
            }
        }
        
        int max = 0;
        for(int i = 1; i < n + 1; i++) {
            max = Math.max(max, node[i][x] + node[x][i]);
        }
        System.out.println(max);
    }
}