[BaekJoon] 10715 JOI 공원 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int squareCount;
    static int roadCount;
    static int variableNum;
    static long totalDistance;
    static long answer;
    static Map<Integer, List<Road>> roads;
    static long[] distances;
    static boolean[] visited;

    static void input() {
        Reader scanner = new Reader();

        squareCount = scanner.nextInt();
        roadCount = scanner.nextInt();
        variableNum = scanner.nextInt();
        roads = new HashMap<>();
        distances = new long[squareCount + 1];
        visited = new boolean[squareCount + 1];
        for (int square = 1; square <= squareCount; square++) {
            roads.put(square, new ArrayList<>());
            distances[square] = Long.MAX_VALUE;
        }

        for (int count = 0; count < roadCount; count++) {
            int square1 = scanner.nextInt();
            int square2 = scanner.nextInt();
            int distance = scanner.nextInt();

            roads.get(square1).add(new Road(square2, distance));
            roads.get(square2).add(new Road(square1, distance));

            totalDistance += distance;
        }
    }

    /*
     * 정비 시에 광장 1로부터 최단 거리가 X 이하인 광장들을 찾아 지하도를 연결해야하므로
     * 다익스트라를 통해 광장 1부터 다른 광장으로의 최단 거리를 찾는다
     * 이때 지하도로 연결된 광장들 사이를 연결하고 있는 도로를 제거해야 한다
     * 다익스트라 알고리즘을 실행하면서 1이 아닌 다른 정점 y를 생각해봤을 때, X가 1부터 y까지의 최단 거리라면
     * 공사 비용은 (C * distances[y] + 철거하지 않은 간선의 길이의 합)이다
     *  - X로 지정할 수 있는 값은 distances 배열에 있는 값(각 광장까지의 최단 거리를 저장하는 배열)이다
     *  - 예를 들어 1이 아닌 다른 한 광장을 y라고 하고 y를 거쳐 가는 경로를 최단 거리로 하는 광장을 z라고 하면
     *  - distances[y]와 distances[z] 사이에 있는 값을 X로 두면 distances[y]를 X로 둘 때와 같은 결과를 얻게 된다
     *      - 결국 y까지 연결된 도로들만 삭제하고 z까지 연결된 도로들은 삭제할 수 없다
     *  - 그러나 공사 비용을 최소로 해야 하기 때문에 distances[y]를 X로 두는 것이 최선의 방법이다
     * 그리고 철거하는 간선들은 1부터 y까지 다익스트라 알고리즘을 통해 이동한 광장들 사이를 연결하는 간선들이다
     * 그렇기 때문에 모든 도로의 길이의 합을 먼저 구해두고 다익스트라를 통해 인접한 광장들로 이동하면서
     * 인접한 광장 중 이전에 방문한 광장이 있다면 그 도로를 제거하기 위해 전체 길이의 합에서 해당 도로의 길이를 빼주고 공사 비용을 계산한다
     */
    static void solution() {
        dijkstra(1);
        System.out.println(answer);
    }

    static void dijkstra(int startSquare) {
        Queue<Road> queue = new PriorityQueue<>();
        long[] distances = new long[squareCount + 1];
        Arrays.fill(distances, Long.MAX_VALUE);

        queue.offer(new Road(startSquare, 0));
        distances[startSquare] = 0;
        answer = totalDistance;

        while (!queue.isEmpty()) {
            Road curRoad = queue.poll();

            if (visited[curRoad.squareNum]) {
                continue;
            }
            if (distances[curRoad.squareNum] < curRoad.distance) {
                continue;
            }

            visited[curRoad.squareNum] = true;
            for (Road next : roads.get(curRoad.squareNum)) {
                int nextSquare = next.squareNum;
                long nextDistance = next.distance;
                if (visited[nextSquare]) {
                    totalDistance -= nextDistance;
                }
            }

            answer = Math.min(answer, totalDistance + variableNum * curRoad.distance);

            for (Road next : roads.get(curRoad.squareNum)) {
                int nextSquare = next.squareNum;
                long nextDistance = next.distance + curRoad.distance;
                if (distances[nextSquare] > nextDistance) {
                    distances[nextSquare] = nextDistance;
                    queue.offer(new Road(nextSquare, nextDistance));
                }
            }
        }
    }

    static class Road implements Comparable<Road> {
        int squareNum;
        long distance;

        public Road(int squareNum, long distance) {
            this.squareNum = squareNum;
            this.distance = distance;
        }

        @Override
        public int compareTo(Road o) {
            if (distance < o.distance) {
                return -1;
            }
            if (distance > o.distance) {
                return 1;
            }
            return 0;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}