[백준] 1238번: 파티 - JAVA

🔗 문제 링크

BOJ 1238번: 파티

1238번: 파티

 

1️⃣ 플로이드-와샬

📝 풀이 과정

학생(i)가 이동하는 경로는 i -> X -> i이다. 따라서 이동하는데 걸리는 시간은 (i -> X) + (X -> i)이므로 학생마다 걸리는 시간을 모두 구할 수 있는 플로이드-와샬 알고리즘이 생각났다.

 

⏱ 시간 복잡도

플로이드 와샬의 경우 시간복잡도가 $O(N^3)$인데, 학생의 수는 최대 1000이므로 세제곱을 하여도 $10^9$ 이므로 1초이내에 해결이 가능하다.

 

💻 코드

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), M = sc.nextInt(), X = sc.nextInt();

        int[][] dist = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++)
            Arrays.fill(dist[i], 1000000);

        for (int i = 0; i < M; i++) {
            int n1 = sc.nextInt(), n2 = sc.nextInt(), t = sc.nextInt();
            dist[n1][n2] = t;
        }


        for (int k = 1; k <= N; k++)
            for (int i = 1; i <= N; i++)
                for (int j = 1; j <= N; j++)
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
        int ans = 0;
        for (int i = 1; i <= N; i++)
            if (i != X)
                ans = Math.max(ans, dist[i][X] + dist[X][i]);

        System.out.println(ans);


    }
}

📊 제출 결과

 

---

 

2️⃣ 다익스트라

📝 풀이 과정

플로이드-와샬로도 충분한 문제이지만, 시간복잡도를 줄일 수 있는 '다익스트라'로도 문제를 풀어보았다.

 

위와 동일하게 경로는 i -> X + X -> i이지만, 다익스트라는 출발점을 지정해 주어야 한다. 따라서 일반적인 다익스트라로 구하기 위해서는 모든 학생들의 시간거리를 계산해야하기 때문에 많은 시간복잡도가 소요되게 된다. 하지만, 그래프를 뒤집고 i -> X를 X -> i로 구할 수 있다면 모든 시작점을 X로 두어 계산하기 때문에 학생마다 계산할 필요가 없게 된다.

 

 

for (int i = 0; i < M; i++) {
  int n1 = sc.nextInt(), n2 = sc.nextInt(), t = sc.nextInt();

  adj[n1].add(new int[]{n2, t});
  reverseAdj[n2].add(new int[]{n1, t});
}

제시된 그래프는 방향 그래프이기 때문에 i -> X를 그냥 구할 수 없어 입력을 받을 때 뒤집어진 인접리스트도 함께 생성해 주었다.

adj로는 정방향인 X -> i의 시간을 구하고, 역방향 그래프인 reverseAdj로는 i -> X의 시간을 구하려고 하였다.

다익스트라를 통해 X -> i dist와 i <- X로 가는 reverseDist를 구해 두개의 합이 최대인 학생을 구하였다.

 

⏱ 시간 복잡도

다익스트라의 시간복잡도는 $O(|E|\log|V|)$이다. 다익스트라를 두 번 사용하지만 중첩해서 사용하는 것이 아니기 때문에 결과적으로 시간복잡도는 $O(|E|\log|V|)$이 된다.

 

💻 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), M = sc.nextInt(), X = sc.nextInt();

        ArrayList<int[]>[] adj = new ArrayList[N + 1];
        ArrayList<int[]>[] reverseAdj = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<>();
            reverseAdj[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            int n1 = sc.nextInt(), n2 = sc.nextInt(), t = sc.nextInt();

            adj[n1].add(new int[]{n2, t});
            reverseAdj[n2].add(new int[]{n1, t});
        }

        int[] dist = dijkstra(X, N, adj);
        int[] reverseDist = dijkstra(X, N, reverseAdj);

        int ans = 0;
        for (int i = 1; i <= N; i++) {
            ans = Math.max(ans, dist[i] + reverseDist[i]);
        }
        System.out.println(ans);

    }

    static int[] dijkstra(int n, int N, ArrayList<int[]>[] adj) {
        int[] dist = new int[N + 1];
        Arrays.fill(dist, 1000000);

        PriorityQueue<int[]> que = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        que.add(new int[]{n, 0});

        while (!que.isEmpty()) {
            int[] cur = que.poll();

            if (dist[cur[0]] < cur[1])
                continue;

            dist[cur[0]] = cur[1];

            for (int[] a : adj[cur[0]]) {
                que.add(new int[]{a[0], cur[1] + a[1]});
            }
        }


        return dist;
    }
}

 

📊 제출 결과