[백준] 161198번 : 달빛 여우 Gold1(골드1) - JAVA[자바]

[Gold I] 달빛 여우 - 16118

문제 링크

성능 요약

메모리: 64780 KB, 시간: 816 ms

분류

데이크스트라, 그래프 이론, 최단 경로

제출 일자

2024년 6월 1일 16:30:08

문제 설명

관악산 기슭에는 보름달을 기다리는 달빛 여우가 한 마리 살고 있다. 달빛 여우가 보름달의 달빛을 받으면 아름다운 구미호로 변신할 수 있다. 하지만 보름달을 기다리는 건 달빛 여우뿐만이 아니다. 달빛을 받아서 멋진 늑대인간이 되고 싶어 하는 달빛 늑대도 한 마리 살고 있다.

관악산에는 1번부터 N번까지의 번호가 붙은 N개의 나무 그루터기가 있고, 그루터기들 사이에는 M개의 오솔길이 나 있다. 오솔길은 어떤 방향으로든 지나갈 수 있으며, 어떤 두 그루터기 사이에 두 개 이상의 오솔길이 나 있는 경우는 없다. 달빛 여우와 달빛 늑대는 1번 나무 그루터기에서 살고 있다.

보름달이 뜨면 나무 그루터기들 중 하나가 달빛을 받아 밝게 빛나게 된다. 그러면 달빛 여우와 달빛 늑대는 먼저 달빛을 독차지하기 위해 최대한 빨리 오솔길을 따라서 그 그루터기로 달려가야 한다. 이때 달빛 여우는 늘 일정한 속도로 달려가는 반면, 달빛 늑대는 달빛 여우보다 더 빠르게 달릴 수 있지만 체력이 부족하기 때문에 다른 전략을 사용한다. 달빛 늑대는 출발할 때 오솔길 하나를 달빛 여우의 두 배의 속도로 달려가고, 그 뒤로는 오솔길 하나를 달빛 여우의 절반의 속도로 걸어가며 체력을 회복하고 나서 다음 오솔길을 다시 달빛 여우의 두 배의 속도로 달려가는 것을 반복한다. 달빛 여우와 달빛 늑대는 각자 가장 빠르게 달빛이 비치는 그루터기까지 다다를 수 있는 경로로 이동한다. 따라서 둘의 이동 경로가 서로 다를 수도 있다.

출제자는 관악산의 모든 동물을 사랑하지만, 이번에는 달빛 여우를 조금 더 사랑해 주기로 했다. 그래서 달빛 여우가 달빛 늑대보다 먼저 도착할 수 있는 그루터기에 달빛을 비춰 주려고 한다. 이런 그루터기가 몇 개나 있는지 알아보자.

입력

첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다.

두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b, 1 ≤ d ≤ 100,000)가 주어진다. 이는 a번 그루터기와 b번 그루터기 사이에 길이가 d인 오솔길이 나 있음을 의미한다.

출력

첫 줄에 달빛 여우가 달빛 늑대보다 먼저 도착할 수 있는 나무 그루터기의 개수를 출력한다.

 

접근 방법

1. 달빛 여우의 가중치는 거리의 * 2

2. 달빛 늑대의 가중치는 그 거리, 혹은 거리의 4배로 처리한다.

3. 우선순위  큐가 아닌 일반 큐를 사용하면 7%에서 시간 초과가 발생한다. 이 점 유의

import java.io.*;
import java.util.*;

public class Main {
    // 그래프 노드
    static class Node {
        int idx;
        int distance;
        Node next;

        public Node(int idx, int distance, Node next) {
            this.idx = idx;
            this.distance = distance;
            this.next = next;
        }
    }

    // 달빛 여우 
    static class Fox {
        int idx;
        int distance;

        public Fox(int next, int distance) {
            this.idx = next;
            this.distance = distance;
        }
    }

    // 달빛 늑대
    static class Wolf {
        int idx;
        int distance;
        int speed;

        public Wolf(int idx, int distance, int speed) {
            this.idx = idx;
            this.distance = distance;
            this.speed = speed;
        }
    }

    static Node[] graph;
    static int[] fox;
    static int[][] wolf;
    static int N;

    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());
        int M = Integer.parseInt(st.nextToken());

        // Input
        graph = new Node[N + 1];
        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 d = Integer.parseInt(st.nextToken()) * 2;

            graph[a] = new Node(b, d, graph[a]);
            graph[b] = new Node(a, d, graph[b]);
        }// Input End

        // 여우 거리 계산
        findFoxPath();

        // 늑대 거리 계산
        findWoldPath();

        // 여우의 거리가 더 적은 곳이라면 answer 값 증가
        int answer = 0;
        for (int i = 1; i <= N; i++) {
            if (fox[i] < Math.min(wolf[0][i], wolf[1][i])) {
                answer++;
            }
        }
        System.out.println(answer);
    }

    // 달빛 늑대 거리 계산
    private static void findWoldPath(){
        PriorityQueue<Wolf> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.distance));
        pq.add(new Wolf(1, 0, 0));

        wolf = new int[2][N + 1];
        Arrays.fill(wolf[0], Integer.MAX_VALUE);
        Arrays.fill(wolf[1], Integer.MAX_VALUE);
        wolf[0][1] = 0;

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

            if (wolf[cur.speed][cur.idx] < cur.distance) continue;
            for (Node node = graph[cur.idx]; node != null; node = node.next) {
                int distance = node.distance * 2;
                int nextSpeed = 0;

                // 다음을 빠르게 갈 수 있을 때 처리 
                if (cur.speed == 0) {
                    distance /= 4;
                    nextSpeed = 1;
                }
                if (cur.distance + distance < wolf[nextSpeed][node.idx]) {
                    wolf[nextSpeed][node.idx] = cur.distance + distance;
                    pq.add(new Wolf(node.idx, wolf[nextSpeed][node.idx], nextSpeed));
                }
            }
        }
    }

    // 달빛 여우 거리 계산 - 일반 다익스트라
    private static void findFoxPath() {
        PriorityQueue<Fox> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.distance));
        pq.add(new Fox(1, 0));

        fox = new int[N + 1]; // 여우 거리 배열
        Arrays.fill(fox, Integer.MAX_VALUE);
        fox[1] = 0;

        while (!pq.isEmpty()) {
            Fox cur = pq.poll();
            if (fox[cur.idx] < cur.distance) continue;
            for (Node node = graph[cur.idx]; node != null; node = node.next) {
                if (cur.distance + node.distance < fox[node.idx]) {
                    fox[node.idx] = cur.distance + node.distance;
                    pq.add(new Fox(node.idx, fox[node.idx]));
                }
            }
        }
    }
}