백준 16118 (달빛 여우) java

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

16118번: 달빛 여우

 

문제

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

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

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

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

 

유형 : 다익스트라

 

접근 방식

• 시간이 굉장이 엄격한 문제라서 다익스트라에서의 모든 최적화를 다 해야 한다.
• 하지만 자바로 문제를 푸는 경우 그것을 넘어서 코드를 줄이는 최적화 또한 필요하다.
• 문제 해결 방식은 간단한데 다익스트라를 2번 수행하면 된다.
  • 달빛 여우가 움직이는 다익스트라
  • 달빛 늑대가 움직이는 다익스트라
    • 늑대의 경우 거리 배열을 2차원으로 선정
      • [i][0]의 경우 해당 지점에서 c / 2 로 움직여야 할 때
      • [i][1]의 경우 해당 지점에서 c * 2 로 움직여야 할 때
• 그리고 입력을 받을 때 거리를 *2로 저장해야 한다. ( 홀수 나누기에 대한 예시가 없기 때문에 !!!! )

전체 코드

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

public class Main {

    static long[] foxDis;

    static long[][] wolfDis;
    static ArrayList<Node>[] graph;
    static int n,m;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new ArrayList[n+1];

        foxDis = new long[n+1];
        wolfDis = new long[n+1][2];

        for(int i = 1 ; i <= n ; i++){
            graph[i] = new ArrayList<>();
        }

        for(int i = 1 ; i <= m ; i++){
            st = new StringTokenizer(br.readLine()," ");
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken()) * 2;

            graph[v1].add(new Node(v2,c));
            graph[v2].add(new Node(v1,c));
        }

        foxMove();
        wolfMove();

        int count = 0;
        for(int i = 2 ; i <= n ; i++){
            if(foxDis[i] < Math.min(wolfDis[i][0],wolfDis[i][1])){
                count++;
            }
        }

        System.out.println(count);
        br.close();
    }
    static void wolfMove(){
        PriorityQueue<Point> pq = new PriorityQueue<>(
                (x,y) -> Long.compare(x.c,y.c)
        );

        for(int i = 2 ; i <= n ; i++){
            for(int j = 0 ; j <= 1 ; j++){
                wolfDis[i][j] = Long.MAX_VALUE;
            }
        }

        wolfDis[1][1] = Long.MAX_VALUE;

        pq.add(new Point(1,0,0));

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

            if(wolfDis[cur.v][cur.type] < cur.c)
                continue;

            for(Node next : graph[cur.v]){
                if(cur.type == 0){

                    long nextDis = cur.c + next.c / 2;

                    if(wolfDis[next.v][1] <= nextDis){
                        continue;
                    }

                    wolfDis[next.v][1] = nextDis;
                    pq.add(new Point(next.v,nextDis,1));
                    continue;
                }else{
                    long nextDis = cur.c + (2* next.c);

                    if(wolfDis[next.v][0] <= nextDis){
                        continue;
                    }

                    wolfDis[next.v][0] = nextDis;
                    pq.add(new Point(next.v,nextDis,0));
                    continue;
                }
            }
        }
    }
    static void foxMove(){
        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> Long.compare(x.c,y.c)
        );

        for(int i = 1 ; i <= n ; i++){
            foxDis[i] = Long.MAX_VALUE;
        }

        foxDis[1] = 0;
        pq.add(new Node(1,0));

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

            if(foxDis[cur.v] < cur.c)
                continue;

            for(Node next : graph[cur.v]){
                if(foxDis[next.v] <= cur.c + next.c){
                    continue;
                }

                foxDis[next.v] = cur.c + next.c;
                pq.add(new Node(next.v,foxDis[next.v]));
            }
        }
    }
    
    static class Node{
        int v;
        long c;

        Node(int v,long c){
            this.v = v;
            this.c = c;
        }
    }

    static class Point{
        int v;
        long c;
        int type;

        Point(int v,long c,int type){
            this.v = v;
            this.c = c;
            this.type = type;
        }
    }
}