백준 1238 - 파티

Java

1238 번 - 파티

문제

접근 방법

모든 NODE에서 출발해 X까지의 왕복거리 중, 최대 왕복 거리를 구하는 문제이다.

각 NODE에서 시작하여, 모든 NODE까지 걸리는 최대 거리를 구한다.

다익스트라의 시간복잡도는 O(N x logN) 이므로, 모든 집에서 출발하여 각 집까지 도달하는데 최대 거리를 구하면, O(N x N x logN) 이 된다.

N은 1000 이므로, 해결 가능하다.

1000 x 1000 x log1000 < 1억

코드

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

public class Main {

    static int n, m, x;
    static boolean[] vis;
    static int[][] map;
    static int[][] cost;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());

        n = stoi(stk.nextToken());
        m = stoi(stk.nextToken());
        x = stoi(stk.nextToken());
        map = new int[n + 1][n + 1];
        cost = new int[n + 1][n + 1];
        

        int a,b,v;
        for(int i = 0; i < m; i++) {
            stk = new StringTokenizer(br.readLine());
            
            a = stoi(stk.nextToken());
            b = stoi(stk.nextToken());
            v = stoi(stk.nextToken());

            map[a][b] = v; 
        }

        // 모든 NODE에서 다른 NODE 까지 걸리는 거리를 계산
        for(int i = 1; i <= n; i++) {
            Dijkstra(i);
        }
        
        int MAX = 0;
        for(int i = 1; i <= n; i++) {
            if(i == x)
                continue;
            MAX = Math.max(MAX, cost[i][x] + cost[x][i]);
        }

        System.out.println(MAX);
    }

    static void Dijkstra(int from){
        vis = new boolean[n + 1];
        int[] node = new int[n + 1];
        Arrays.fill(node, Integer.MAX_VALUE);

        int curN = 0;
        node[from] = 0;
        while(true){
            int min = Integer.MAX_VALUE;
            for(int i = 1; i <= n; i++) {
                if(!vis[i] && min > node[i]) {
                    min = node[i];
                    curN = i;
                } 
            }
            if(min == Integer.MAX_VALUE)
                break;

            vis[curN] = true;
            for(int i = 1; i <= n; i++) {
                if(!vis[i] && map[curN][i] != 0) {
                    if(node[i] > node[curN] + map[curN][i]) {
                        node[i] = node[curN] + map[curN][i];
                    }
                }
            }
            
        }

        // 출발 지점에서, 각 지점까지 걸리는 최소 거리를 배열로 저장
        for(int i = 1; i <= n; i++) {
            cost[from][i] = node[i];
        }

    }

    public static int stoi(String str){
        return Integer.parseInt(str);
    }
}