[PS] BOJ1238 파티 ( floyd-warshall ) with JAVA

1238번: 파티

 

 

◎ 문제풀이

 

다익스트라 알고리즘 문제로 알려져 있는데, 문제를 보니 플로이드 워셜 알고리즘이 더 어울린다고 생각했다. 시작점이 정해져 있지 않았고 모든 노드를 기준으로 하기 때문이다. 플로이드 워셜은 삼중for문을 구현하므로 시간초과를 조심해야 하는데, 시간제한이 1초이고 n이 1000이하라 삼중for문을 돌리면 얼추 시간초과가 걸리지 않는다고 생각했다. 

 

[Algorithm] 플로이드-워셜(Floyd-Warshall) 알고리즘이란?

 

알고리즘은 위 포스팅을 참고하면 된다. 참고로 int 정수 범위를 신경쓰지 않아서 몇번 틀렸다. 그래프에 무한대를 넣을때 Integer.MAX_VALUE를 사용했다. 문제는 int의 최대값과 최대값을 더해서 다시 int에 넣는 실수를 했다. int의 최댓값을 사용할때는 연산에 유의해야 겠다.

 

 

◎ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

import static java.lang.Math.*;

//BOJ1238 파티
public class Main {

    static int[][] graph;
    static int n;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());
        graph = new int[n+1][n+1];

        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j) graph[i][j] = 0;
                else graph[i][j] = 1000000000;
            }
        }

        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());

            graph[start][end] = value;
        }

        for(int mid=1;mid<=n;mid++){
            for(int start=1;start<=n;start++){
                for(int end=1;end<=n; end++){
                    int curr = graph[start][end];
                    int value = graph[start][mid] + graph[mid][end];
                    graph[start][end] = min(curr,value);
                }
            }
        }

        int ans = 0;
        for(int i=1;i<=n;i++){
            ans = max(ans, graph[i][x] + graph[x][i] );
        }

        System.out.println(ans);
    }
}