[백준 1238번 / Java] 파티 - 다익스트라(Dijkstra)

 

 

문제 난이도

GOLD III

 

 

문제 링크

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

 

 

 

풀이

[알고리즘] 다익스트라(Dijkstra) 알고리즘

 

위의 다익스트라 알고리즘을 사용해서 구현한 문제이다.

 

 

 

 

문제 예시를 그림으로 표현해보았다.

목적지로의 최단거리만 구하면 됐던 기본적인 다익스트라 알고리즘 구현 문제에서, 반대로 2에서 각 노드의 최단 경로를 한번 더 구해주기만 하면 된다. (A -> X, X -> A)

 

private static int[] dijkstra(List<List<Node>> graph, int n, int start) {
    PriorityQueue<Node> pq = new PriorityQueue<>();
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    boolean[] visited = new boolean[n + 1];

    dist[start] = 0;
    pq.offer(new Node(start, 0));

    while (!pq.isEmpty()) {
        Node current = pq.poll();
        int curNode = current.node;

        if (visited[curNode]) continue;
        visited[curNode] = true;

        for (Node neighbor : graph.get(curNode)) {
            if (dist[neighbor.node] > dist[curNode] + neighbor.cost) {
                dist[neighbor.node] = dist[curNode] + neighbor.cost;
                pq.offer(new Node(neighbor.node, dist[neighbor.node]));
            }
        }
    }

    return dist;
}

 

기본적인 다익스트라 구현 코드이다. 이를 문제에 맞게, X로 가는 최단거리를 구할 때, X에서 각 노드로 가는 최단거리를 구할 때, 총 두 번 사용해서 문제를 해결하면 된다.

 

List<List<Node>> city = new ArrayList<>();
for (int i = 0; i <= N; i ++) {
    city.add(new ArrayList<>());
}

for (int i = 0; i < M; i ++) {
    st = new StringTokenizer(br.readLine());
    int start = Integer.parseInt(st.nextToken());
    int dest = Integer.parseInt(st.nextToken());
    int cost = Integer.parseInt(st.nextToken());

    city.get(start).add(new Node(dest, cost));
}

List<List<Node>> reverseCity = new ArrayList<>();
for (int i = 0; i <= N; i++) {
    reverseCity.add(new ArrayList<>());
}
for (int i = 1; i <= N; i++) {
    for (Node node : city.get(i)) {
        reverseCity.get(node.node).add(new Node(i, node.cost));
    }
}

 

왕복 경로를 계산하기 위해 기존의 그래프의 구현 리스트와, 역방향 그래프를 따로 만들었다.

원래 그래프에서 1....N번째에서 출발하여 X로 가는 최단거리를 계산하고, 역방향 그래프에서 X에서 출발하여 각 노드로 가는 최단 거리를 계산할 수 있다.

 

 

package bakjoon;

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

public class Main {

    static class Node implements Comparable<Node> {
        int node;
        int cost;
        public Node (int node, int cost) {
            this.node = node;
            this.cost = cost;
        }

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

    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());

        List<List<Node>> city = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            city.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            city.get(start).add(new Node(dest, cost));
        }

        int[] toX = dijkstra(city, N, X);

        List<List<Node>> reverseCity = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            reverseCity.add(new ArrayList<>());
        }
        for (int i = 1; i <= N; i++) {
            for (Node node : city.get(i)) {
                reverseCity.get(node.node).add(new Node(i, node.cost));
            }
        }

        int[] fromX = dijkstra(reverseCity, N, X);

        int max = 0;
        for (int i = 1; i <= N; i++) {
            max = Math.max(max, toX[i] + fromX[i]);
        }

        System.out.println(max);
    }

    private static int[] dijkstra(List<List<Node>> graph, int n, int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        boolean[] visited = new boolean[n + 1];

        dist[start] = 0;
        pq.offer(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int curNode = current.node;

            if (visited[curNode]) continue;
            visited[curNode] = true;

            for (Node neighbor : graph.get(curNode)) {
                if (dist[neighbor.node] > dist[curNode] + neighbor.cost) {
                    dist[neighbor.node] = dist[curNode] + neighbor.cost;
                    pq.offer(new Node(neighbor.node, dist[neighbor.node]));
                }
            }
        }

        return dist;
    }
}