1238. 파티

문제

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

---

 

접근 1 ⭕

• 플로이드 워셜 (00:21:37)

각각의 1~N번 마을에 살고 있는 학생들이 X번 마을을 왕복할 때 가장 시간이 많이 걸리는 학생이 누군지 찾는 문제이다. 즉, 1~N번 마을에서 X번 마을까지의 최단 거리를 구하고, X번 마을에서 1~N번 마을까지의 최단 거리를 구한 다음에 1↔X, 2↔X, …, N↔X 중 최대값을 구하면 되는 문제이다.

 

두 가지의 최단 거리를 한번에 구하는 가장 쉬운 방법이 바로 ‘플로이드 워셜’이다. 플로이드 워셜은 모든 정점에서 시작해 모든 정점까지의 최단 거리를 구하는 알고리즘이다!

---

 

접근 2 🔺

• 다익스트라 (00:30:12)

두 번째 해결 방법으로는 다익스트라가 있다.

💡 1~N번 마을에서 X번 마을까지의 최단 거리를 구하고, X번 마을에서 1~N번 마을까지의 최단 거리를 구한 다음에 1↔X, 2↔X, …, N↔X 중 최대값을 구하면 되는 문제

 

위의 접근법에서 말했듯이 다익스트라 알고리즘을 통해 1~N번 마을에서 X번 마을까지의 최단 거리와 X번 마을에서 1~N번 마을까지의 최단 거리를 구해서 둘의 합 중 최대값을 출력해도 된다. 그런데 좀 생각해보면 다익스트라는 어느 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘인데, 어떻게 ‘1~N번 마을에서 X번 마을까지의 최단 거리’를 구할 수 있을까? 단순히 1~N번 반복하여 구하는 것일까?

 

처음에 이렇게 생각하였는데, 결론부터 말하면 아니다! 단순히 그래프의 간선들을 뒤집으면 된다. 뒤집은 그래프를 가지고 X번 정점을 기준으로 다익스트라 알고리즘을 돌리면 실제로는 X 정점에서 1~N 정점까지의 최단 거리지만 논리적으로는 1~N 정점에서 X 정점까지의 최단 거리가 되는 것이다!

 

그래프에 대한 발상의 전환이 조금 필요한 문제였다. 이게 생각안나서 질문 게시판 봤다..

참고 : https://www.acmicpc.net/board/view/113888

---

 

소스 코드 💡

// 플로이드 워셜
public class BOJ_1238 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());

        int[][] shortest = new int[n+1][n+1];
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (i == j) shortest[i][j] = 0;
                else shortest[i][j] = 987654321;
            }
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            shortest[v1][v2] = w;
        }

        for (int v1 = 1; v1 < n+1; v1++) {
            for (int v2 = 1; v2 < n + 1; v2++) {
                for (int v = 1; v < n + 1; v++) {
                    shortest[v2][v] = Math.min(shortest[v2][v], shortest[v1][v] + shortest[v2][v1]);
                }
            }
        }

        int max = 0;
        for (int i = 1; i < n + 1; i++) {
            if (i == x) continue;
            max = Math.max(shortest[i][x] + shortest[x][i], max);
        }
        System.out.println(max);
    }
}

// 다익스트라
public class BOJ_1238_2 {

    private static class Vertex {
        int v, w;

        public Vertex(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());

        LinkedList<LinkedList<Vertex>> graph1 = new LinkedList<>();
        LinkedList<LinkedList<Vertex>> graph2 = new LinkedList<>();
        for (int i = 0; i < n+1; i++) {
            graph1.add(new LinkedList<>());
            graph2.add(new LinkedList<>());
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            graph1.get(v1).add(new Vertex(v2, w));
            graph2.get(v2).add(new Vertex(v1, w));
        }

        int[] xTov = dijkstra(graph1, x, n);
        int[] vTox = dijkstra(graph2, x, n);

        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) max = Math.max(max, xTov[i] + vTox[i]);
        System.out.println(max);
    }

    private static int[] dijkstra(LinkedList<LinkedList<Vertex>> graph, int v, int n) {
        int[] shortest = new int[n+1];
        Arrays.fill(shortest, 987654321);
        shortest[v] = 0;

        boolean[] visited = new boolean[n+1];

        for (int i = 1; i <= n; i++) {
            int minV = 0;
            int value = Integer.MAX_VALUE;
            for (int j = 1; j <= n; j++) {
                if (value > shortest[j] && !visited[j]) {
                    value = shortest[j];
                    minV = j;
                }
            }

            visited[minV] = true;
            for (Vertex vertex : graph.get(minV)) {
                shortest[vertex.v] = Math.min(shortest[vertex.v], shortest[minV] + vertex.w);
            }
        }

        return shortest;
    }
}