[백준 Baekjoon] 1238번 파티 - JAVA

백준 Baekjoon 1238번 파티 - JAVA

문제 풀이

다익스트라 알고리즘을 사용하여 푸는 문제이다. 주로 양방향 그래프가 주어지고 다익스트라 알고리즘을 활용하여 푸는 문제들이 나왔는데, 이번에는 단방향 그래프가 주어졌다.


모든 마을에서 다익스트라를 사용하여 최단거리를 구하는 방법도 존재하지만, X를 출발지로 지정하면 다익스트라 알고리즘을 두번만 사용하여 구할 수 있다.


정방향과 역방향 그래프와 각각의 최단 거리를 저장할 배열이 필요하다.


주어진 단방향 그래프를 그대로 입력받고 다익스트라를 사용하면 모든 마을에서 X까지의 최단거리를 구할 수 있다. 하지만 반대로 X에서 마을로 돌아오는 길을 구하기 위해서는 입력 받는 그래프를 역으로 바꿔 저장한 다음 다익스트라를 사용하여 구해야 한다.

소스 코드

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

public class Main {
    public static int N, M, X;

    public static List<Node>[] forwardList;
    public static List<Node>[] reverseList;

    public static int[] forward;
    public static int[] reverse;

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

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

        forwardList = new List[N + 1];
        reverseList = new List[N + 1];

        forward = new int[N + 1];
        reverse = new int[N + 1];

        for (int i = 0; i <= N; i++) {
            forwardList[i] = new ArrayList<>();
            reverseList[i] = new ArrayList<>();
        }

        Arrays.fill(forward, Integer.MAX_VALUE);
        Arrays.fill(reverse, Integer.MAX_VALUE);
        forward[X] = reverse[X] = 0;

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int T = Integer.parseInt(st.nextToken());

            forwardList[A].add(new Node(B, T));
            reverseList[B].add(new Node(A, T));
        }

        dijkstra(forwardList, forward);
        dijkstra(reverseList, reverse);


        int answer = 0;
        for (int i = 1; i <= N; i++) {
            answer = Math.max(answer, forward[i] + reverse[i]);
        }
        System.out.println(answer);
    }

    public static void dijkstra(List<Node>[] list, int[] min) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        boolean[] visit = new boolean[N + 1];

        pq.add(new Node(X, 0));

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (visit[cur.dest]) continue;
            visit[cur.dest] = true;

            for (Node next : list[cur.dest]) {
                if (min[next.dest] > min[cur.dest] + next.dist) {
                    min[next.dest] = min[cur.dest] + next.dist;
                    pq.offer(new Node(next.dest, min[next.dest]));
                }
            }
        }
    }

    public static class Node implements Comparable<Node>{
        int dest;
        int dist;

        public Node(int dest, int dist) {
            this.dest = dest;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node o) {
            return this.dist - o.dist;
        }
    }

}

번외

모든 마을에서 다익스트라를 사용하여 2차원 배열에 최단거리를 저장하여 구한 방법이다. 모든 마을에서 다익스트라를 사용하기 때문에 위의 방법보다 3배의 시간이 더 걸렸다.

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

public class Main {
    public static int N, M, X;

    public static List<Node>[] list;
    public static int[][] min;

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

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

        list = new List[N + 1];
        min = new int[N + 1][N + 1];

        for (int i = 0; i <= N; i++) {
            list[i] = new ArrayList();
            Arrays.fill(min[i], Integer.MAX_VALUE);
            min[i][i] = 0;
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int T = Integer.parseInt(st.nextToken());

            list[A].add(new Node(B, T));
        }

        for (int i = 1; i <= N; i++) {
            dijkstra(i);
        }

        int answer = 0;
        for (int i = 1; i <= N; i++) {
            answer = Math.max(answer, min[i][X] + min[X][i]);
        }
        System.out.println(answer);
    }

    public static void dijkstra(int n) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        boolean[] visit = new boolean[N + 1];

        pq.add(new Node(n, 0));

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (visit[cur.dest]) continue;
            visit[cur.dest] = true;

            for (Node next : list[cur.dest]) {
                if (min[n][next.dest] > min[n][cur.dest] + next.dist) {
                    min[n][next.dest] = min[n][cur.dest] + next.dist;
                    pq.offer(new Node(next.dest, min[n][next.dest]));
                }
            }
        }
    }

    public static class Node implements Comparable<Node>{
        int dest;
        int dist;

        public Node(int dest, int dist) {
            this.dest = dest;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node o) {
            return this.dist - o.dist;
        }
    }

}