[백준]1238. 파티

📄 링크

파티

---

💡 문제 분석

N개의 정점, M개의 간선을 가진 그래프입니다.
무향 그래프였다면 도착지인 X가 정해져 있어서 한 번의 다익스트라로 가능했을 것 같은데 방향 그래프였기 때문에 플로이드-와샬을 쓰기로 했습니다.

N이 1000이기 때문에 플로이드-와샬의 시간 복잡도 O(N^3)이므로 빠듯해보였습니다.
그래서 플로이드-와샬에서 i에서 k로 가는 정점이 없다면 건너 뛰는 가지치기를 적용했습니다.

---

⌨️ 코드

import java.util.Arrays;
import java.util.Scanner;

public class _1238_파티 {

    static int N, M, X;
    static int[][] adj;

    public static void main(String[] args) {
        // 입력
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        X = sc.nextInt();
        adj = new int[N + 1][N + 1];
        for(int i = 1; i < N + 1; i++) {
            Arrays.fill(adj[i], 1000000);
        }
        for(int i = 1; i < N + 1; i++)
            adj\[i\][i] = 0;
        for(int i = 0; i < M; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            int w = sc.nextInt();
            adj\[from\][to] = w;
        }

        // 플로이드-와샬 시작
        for(int k = 1; k < N + 1; k++) {
            for(int i = 1; i < N + 1; i++) {
                if(adj\[i\][k] >= 1000000)
                    continue;
                for(int j = 1; j < N + 1; j++) {
                    adj\[i\][j] = Math.min(adj\[i\][j], adj\[i\][k] + adj\[k\][j]);
                }
            }
        }

        // 최대 소요시간 계산
        int ret = 0;
        for(int i = 1; i < N + 1; i++)
            ret = Math.max(ret, adj[i][X] + adj[X][i]);

        System.out.println(ret);
    }
}

---

📋 회고

• 최단 거리
• 플로이드 와샬
• 시간 복잡도