[백준 골드1] 16118번: 달빛 여우 (다익스트라) - Java

"스파르타코딩클럽 작심큰일 챌린지" 1일차 챌린저 문제

---

16118번: 달빛 여우

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

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

관악산에는 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 
5 6
1 2 3
1 3 2
2 3 2
2 4 4
3 5 4
4 5 3
예제 출력 1 

1

---

알고리즘: 그래프, 최단 경로, 다익스트라 알고리즘

풀이

그래프상에서 다익스트라 알고리즘으로 최단 거리를 탐색하는 문제. 달빛 여우와 달빛 늑대는 같은 그래프의 같은 시작점에서 서로 다른 속도 규칙으로 이동한다.

 

<최단 거리 저장 관련>

- 달빛 여우는 distance[정점]으로 충분했다.

- 달빛 늑대는 매 이동마다 빠른 상태(간선 가중치/2)와 느린 상태(가중치×2)가 번갈아 적용되므로, 각 정점마다 상태별 최단 거리를 저장하기 위해 2차원 배열 distance[정점][상태]를 만들어 사용했다. (또한 /2 연산에서 소수점 값이 손실되는 것을 막기 위해 그래프에 오솔길 길이 저장시 d*2한 값을 저장했다.)

<달빛 늑대의 속도 상태 확인>

- Node 클래스는 index, weight외에도 늑대만 사용할 state 필드를 추가해 사용했다.

- Node 클래스에서 Comparable 인터페이스를 구현하고 compareTo 메소드를 오버라이딩해, 우선 순위 클래스 사용 시 정렬 기준을 weight 오름차순으로 설정했다.

- 우선순위 큐에서 Node 객체를 꺼냈을 때 객체의 state를 확인하여 다음 이동 속도를 연산하고, 다음 Node 객체를 넣을 때 nextState를 1-state로 연산했다.

<시간 초과 방지>

- 그래프의 인접 리스트를 LinkedList가 아닌 ArrayList로 구현해야 시간 초과가 나지 않았다. (ArrayList: 랜덤/순차 접근 O(1), LinkedList: 순차 접근 O(N))

- 더 최단거리를 선택하게끔 하면 visited 배열을 사용하지 않아도, distance 배열만으로 경로 최적화 및 pruning이 가능했다. (시간복잡도 O(M log N))

  - Pruning: 알고리즘에서 불필요한 탐색, 연산 등을 미리 잘라내어 효율을 높이는 기법. 아래에서는 우선순위 큐에서 꺼낸 노드의 가중치가(curr.weight)가 기존 그 노드의 최단 거리(distance[u])보다 큰 경우 continue하도록 했다.

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

public class Main
{
    static class Node implements Comparable<Node> {
        int index, weight, state; // state는 늑대만 사용
        
        Node(int index, int weight) {
            this.index = index;
            this.weight = weight;
            this.state = 0;
        }
        
        Node(int index, int weight, int state) {
            this.index = index;
            this.weight = weight;
            this.state = state;
        }
        
        @Override
        public int compareTo(Node n) {
            return Integer.compare(this.weight, n.weight);
        } 
    }
    
    static int n;
    static List<List<Node>> graph;
    
    private static int[] dijkstraForFox(){
        int[] distance = new int[n]; // [노드]
        Arrays.fill(distance, Integer.MAX_VALUE);
        PriorityQueue<Node> pq = new PriorityQueue<>();
        distance[0] = 0; // 시작점은 0
        pq.add(new Node(0, 0)); // 점, 가중치
        
        while(!pq.isEmpty()) {
            Node curr = pq.poll();
            int u = curr.index;
            int currDist = curr.weight;
            if(currDist > distance[u])
                continue;
            for(Node n : graph.get(u)) {
                int v = n.index;
                int w = n.weight;
                if(currDist + w < distance[v]){
                    distance[v] = currDist + w;
                    pq.add(new Node(v, distance[v]));
                }
            }
        }
        return distance;
    }
    
    private static int[][] dijkstraForWolf(){
        int[][] distance = new int[n][2]; // [노드][상태], 0=빠름, 1=느림
        for (int[] row : distance)
            Arrays.fill(row, Integer.MAX_VALUE);
        PriorityQueue<Node> pq = new PriorityQueue<>();
        distance[0][0] = 0; // 시작점은 0
        pq.add(new Node(0, 0, 0)); // 점, 가중치, 상태
        
        while(!pq.isEmpty()) {
            Node curr = pq.poll();
            int u = curr.index;
            int currDist = curr.weight;
            int state = curr.state;
            if (currDist > distance[u][state])
                continue;
            for (Node n : graph.get(u)) {
                int v = n.index;
                int w = state == 1 ? n.weight * 2 : n.weight / 2;
                int nextState = 1 - state;
                if (currDist + w < distance[v][nextState]) {
                    distance[v][nextState] = currDist + w;
                    pq.add(new Node(v, distance[v][nextState], nextState));
                }
            }
        }
        return distance;
    }
    
    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());
        graph = new ArrayList<>();
        for(int i=0; i<n; i++) {
            graph.add(new ArrayList<>());
        }
        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; // /2 고려
            graph.get(a-1).add(new Node(b-1, d));
            graph.get(b-1).add(new Node(a-1, d));
        }
        int[] dFox = dijkstraForFox();
        int[][] dWolf = dijkstraForWolf();
        int count = 0;
        for(int i=0; i<n; i++) {
            if (dFox[i] < dWolf[i][0] && dFox[i] < dWolf[i][1]) count++;
        }
        System.out.println(count);
    }
}