(BOJ)1238 파티

1238 파티

https://www.acmicpc.net/problem/1238

 

TIPS

1. 최단경로 문제

2. 플로이드 다익스트라 알고리즘을 해결할 수 있다.

3. 플로이드로 풀경우 O(|V|^3^) 속도 때문에 안풀리 수 있다고 하는데, 조건과 관계없이 풀수 있다.

4. 플로이드로 풀경우 단순히 학생집에서 파티장의 최단거리, 파티장에서 학생집까지의 최단거리를 더해서 값을 구할 수 있다.

5. 다익스트라로 풀경우, 파티장에서 학생집까지는 쉽게 구할수 있다. 하지막 역은 모든 정점을 다시 구해야 하는 불편함이 있다. 이를 해결하기 위해서, 간선의 방향을 바꿔서 파티장에서 각 노드까지의 간선의 합을 구하면 쉽게 구할 수 있다고 한다.

 

CODE

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
​
public class BOJ_1238 {
    static int MAX_TIME = 99000;
​
    static int[][] d;
    static int N; // the number of student
    static int M; // the number of road
    static int X; // goal index
​
​
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
​
    public static void main(String[] args) throws IOException {
​
        // init
        N = readInt();
        M = readInt();
        X = readInt();
        d = new int[N + 1][N + 1];
​
        for(int i = 1; i <= N; i++){
            Arrays.fill(d[i], MAX_TIME);
            d[i][i] = 0;
        }
​
        for (int i = 1; i <= M; i++) {
            int fromIndex = readInt();
            int toIndex = readInt();
            int value = readInt();
​
            d[fromIndex][toIndex] = value;
        }
​
        floyd();
​
        // solve
        int max = 0;
        for(int i = 1; i <= N; i++){
            if(i == X) continue;
            max = Math.max(max , d[i][X] + d[X][i]);
        }
​
        // print
        System.out.println(max);
    }
​
    static void floyd() {
​
        for(int k = 1; k <= N; k++){
            for(int i = 1; i <= N; i++){
                for(int j = 1; j <= N; j++){
                    d[i][j] = d[i][j] > d[i][k] + d[k][j] ? d[i][k] + d[k][j] : d[i][j];
                }
            }
        }
​
    }
​
    static int readInt() throws IOException {
        if (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
​
        return Integer.parseInt(st.nextToken());
    }
}

 

DEBUG

처음에 최대값을 101일로 잡았었다. 하지만 계속문제가 생겼다.

하나의 길의 최대값은 100이지만, 여러 길을 건너다 보면 더 커질 수있다.

V의 개수가 10개라면, 최대값은 100*10 이기 때문에 101을 넘는다.

문제에서는 모든 정점들이연결된다고 말했지만, 연결되지 않을 경우도 있을 수 있기때문에 최단거리 최대값을 구할때 좀더 신경써야 할 것 같다.