BOJ G3 1238 파티 JAVA

1238번: 파티

---

문제 읽기

처음 문제를 봤을 때.. 다익스트라 같은데, 다익스트라를 너무 많이 돌리는데? 싶었다. N명의 학생이, 각각 N개의 마을을 출발점으로 X까지 최소 거리 구하려면 다익스트라 N번, 게다가 X를 출발점으로 다른 N개의 마을까지 최소 거리 구하려면 다익스트라 1번.. 총 N+1번의 다익스트라인데? 싶었다. 그래도 N이 1000이라서 일단 괜찮을 것 같아서 (조금 찜찜하지만) N+1번의 다익스트라로 문제를 풀었다.

---

문제 풀기

딱히 다른 다익스트라와 다를 건 없었고, 최소 거리를 저장하는 배열만 NxN 2차원으로 만들어서 N+1번의 다익스트라를 수행하였다. 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static class Node{
        int no;
        int cost;
        public Node(int no, int cost){
            this.no = no;
            this.cost = cost;
        }
    }
    static int N, M, X;
    static ArrayList<Node>[] graph;
    static int[][] distToX;
    static int[] distToOthers;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(in.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());

        //그래프 입력
        graph = new ArrayList[N+1];
        for (int i = 0; i < N+1; i++){
            graph[i] = new ArrayList<>();
        }
        while(M-- > 0){
            st = new StringTokenizer(in.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            graph[start].add(new Node(end, cost));
        }

        //다익스트라
        //1. 각 모든 노드들 ~ 다른 모든 노드들. N번의 다익스트라 시작.
        distToX = new int[N+1][N+1];
        for (int start = 1; start <= N; start++){
            dijkstra(distToX[start], start);
        }
        //2. X에서 ~ 모든 노드 == distToX[X][~~];

        //모든 학생들이 왔다갔다 하는 비용의 최댓값
        int maxVal = 0;
        for (int student = 1; student <= N; student++){
            maxVal = Math.max(maxVal, distToX[student][X] + distToX[X][student]);
        }
        System.out.println(maxVal);
    }

    static int INF = Integer.MAX_VALUE - 1000;
    private static void dijkstra(int[] dist, int start) {
        //pq, visited, dist
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.cost - o2.cost;
            }
        });
        boolean[] visited = new boolean[N+1];

        //init
        pq.offer(new Node(start, 0));
        Arrays.fill(dist, INF);
        dist[start] = 0;

        //logic
        while(!pq.isEmpty()){
            Node cur = pq.poll();
            if (visited[cur.no]) continue;
            visited[cur.no] = true;

            for (Node adj : graph[cur.no]){
                if (dist[adj.no] > dist[cur.no] + adj.cost){
                    dist[adj.no] = dist[cur.no] + adj.cost;
                    pq.offer(new Node(adj.no, dist[adj.no]));
                }
            }
        }
    }
}

바로 정답은 나왔다. 하지만 시간이 넘 오래 걸리는 걸..

JAVA로 푼 다른 사람들 채점 기록을 봤더니 엄청 적은 사람이 있었다.. 이게 뭐지!?!? 싶어서 바로 봤더니 다익스트라를 두 번만 썼다..!!

 

글 읽기 - 1238 파티 제가 성공은 하였지만 더 좋은 방법이있나 싶어 질문드립니다.

위 글을 봐도 이해할 수 있는데, 다시 한 번 정리해보겠다.

 

문제에서 원하는 것은 다음 두 가지이다.

1. 다른 모든 노드를 출발점으로 하여 X까지의 최소 거리
2. X를 출발점으로 하여 다른 모든 노드까지의 최소 거리

2번은 직관적으로 봤을 때도 1번의 다익스트라로 풀 수 있고, 나도 2번은 그렇게 해결했다.

 

하지만 1번이 문제이다. 다익스트라는 하나의 출발점에서 다른 모든 노드까지의 최소 거리를 구할 수 있는데, 1번은 뭐랄까 N번의 다익스트라를 수행하기에는 효율(?)이 너무 안 나온다. 다시 말하자면 N번의 다익스트라를 해도 도착점은 X만 필요하기 때문에.. 흠.. 뭔가 쓸데없이 다른 정보를 구하는 느낌이다.

 

그래서! 우리는 그래프를 뒤집어 볼 수 있다.

문제에서 주어지는 것은 비용이 있는 단방향 그래프이다. 이를 그림으로 그려보면 다음과 같다.

 

그리고 여기에서 1번을 표시하면 다음과 같다.

 

이 그래프의 간선을 반대로 뒤집는다면? 다음과 같이 될 것이다.

 

즉, X에서 시작해서 다른 모든 노드로의 dijkstra로 구할 수 있는 것이다!!

 

이렇게 N+1번의 Dijkstra를 2번의 Dijkstra로 해결할 수 있다.

---

코드

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_G3_1238_파티 {
    static class Node{
        int no;
        int cost;
        public Node(int no, int cost){
            this.no = no;
            this.cost = cost;
        }
    }
    static int N, M, X;
    static ArrayList<Node>[] graph;
    static ArrayList<Node>[] reverseGraph;
    static int[] distFromX;
    static int[] distToX;

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

        StringTokenizer st = new StringTokenizer(in.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());

        //그래프 입력
        graph = new ArrayList[N+1];
        reverseGraph = new ArrayList[N+1];
        for (int i = 0; i < N+1; i++){
            graph[i] = new ArrayList<>();
            reverseGraph[i] = new ArrayList<>();
        }
        while(M-- > 0){
            st = new StringTokenizer(in.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            graph[start].add(new Node(end, cost));
            reverseGraph[end].add(new Node(start, cost));
        }

        //다익스트라
        distFromX = new int[N+1];
        distToX = new int[N+1];
        //1. X에서 다른 모든 노드까지 다익스트라 1번
        dijkstra(distFromX, graph, X);
        //2. 간선을 뒤집고 X에서 다른 모든 노드까지 다익스트라 1번
        //간선 뒤집기
        dijkstra(distToX, reverseGraph, X);

        //모든 학생들이 왔다갔다 하는 비용의 최댓값
        int maxVal = 0;
        for (int student = 1; student <= N; student++){
            maxVal = Math.max(maxVal, distToX[student] + distFromX[student]);
        }
        System.out.println(maxVal);
    }

    static int INF = Integer.MAX_VALUE - 1000;
    private static void dijkstra(int[] dist, List<Node>[] graph, int start) {
        //pq, visited, dist
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.cost - o2.cost;
            }
        });
        boolean[] visited = new boolean[N+1];

        //init
        pq.offer(new Node(start, 0));
        Arrays.fill(dist, INF);
        dist[start] = 0;

        //logic
        while(!pq.isEmpty()){
            Node cur = pq.poll();
            if (visited[cur.no]) continue;
            visited[cur.no] = true;

            for (Node adj : graph[cur.no]){
                if (dist[adj.no] > dist[cur.no] + adj.cost){
                    dist[adj.no] = dist[cur.no] + adj.cost;
                    pq.offer(new Node(adj.no, dist[adj.no]));
                }
            }
        }
    }
}