[BaekJoon] 16118 달빛 여우 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static final int START = 1;
    static int N, M;
    static Map<Integer, List<Edge>> edges;

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

        N = scanner.nextInt();
        M = scanner.nextInt();
        edges = new HashMap<>();
        for(int vertex = 1; vertex <= N; vertex++)
            edges.put(vertex, new ArrayList<>());

        for(int edge = 0; edge < M; edge++) {
            // 달빛 늑대는 2배 빠르게, 2배 느리게를 반복하여 거리를 1/2배, 2배를 진행해야 한다
            // 이때 미리 거리를 2배 해놓으면 소숫점이 나올 일이 없으니 double 타입을 쓸 필요가 없어진다
            // 그러므로 미리 거리를 2배 해놓는다
            int vertex1 = scanner.nextInt(), vertex2 = scanner.nextInt(), distance = scanner.nextInt() * 2;
            edges.get(vertex1).add(new Edge(vertex2, distance));
            edges.get(vertex2).add(new Edge(vertex1, distance));
        }
    }

    static void solution() {
        // 달빛 여우는 일정한 속도로 이동하기 때문에 일반적인 다익스트라를 통해 시작 지점부터 다른 지점으로의 최소 거리를 구한다
        long[] fox = dijkstraFox(START);
        // 달빛 늑대는 2배 빠르게, 2배 느리게를 반복하기 때문에
        // 0, 1의 상태값을 이용해 적용시키며 다익스트라를 통해 시작 지점부터 다른 지점으로의 최소 거리를 구한다
        long[][] wolf = dijkstraWolf(START);

        int answer = 0;
        // 달빛 여우가 더 빨리 도착할 수 있는 곳을 찾아 해당 위치들의 수를 구한다
        for(int vertex = 1; vertex < fox.length; vertex++)
            if(fox[vertex] < Math.min(wolf[0][vertex], wolf[1][vertex])) answer++;

        System.out.println(answer);
    }

    static long[][] dijkstraWolf(int start) {
        PriorityQueue<Edge> queue = new PriorityQueue<>();
        // distance[0][N] : 2배 속도로 N까지 왔을 때 최소 거리
        // distance[1][N] : 1/2배 속도로 N까지 왔을 때 최소 거리
        long[][] distance = new long[2][N + 1];
        for(int idx = 0; idx < distance.length; idx++)
            Arrays.fill(distance[idx], Long.MAX_VALUE);

        distance[0][start] = 0;
        queue.offer(new Edge(start, 0, 0));

        while(!queue.isEmpty()) {
            Edge cur = queue.poll();
            if(distance[cur.state][cur.vertex] < cur.distance) continue;

            for(Edge next : edges.get(cur.vertex)) {
                int nextVertex = next.vertex;
                int nextState = 1 - cur.state; // 다음 상태값을 구함
                // 현재 상태값에 따라 거리를 1/2배 할지, 2배를 할지 결정하여 그만큼을 다음 이동 거리에 더한다
                long nextDist = cur.distance + (cur.state == 0 ? next.distance / 2 : next.distance * 2);

                if(distance[nextState][nextVertex] > nextDist) {
                    distance[nextState][nextVertex] = nextDist;
                    queue.offer(new Edge(nextVertex, nextDist, nextState));
                }
            }
        }

        return distance;
    }

    static long[] dijkstraFox(int start) {
        PriorityQueue<Edge> queue = new PriorityQueue<>();
        long[] distance = new long[N + 1];
        Arrays.fill(distance, Long.MAX_VALUE);

        distance[start] = 0;
        queue.offer(new Edge(start, 0));

        while(!queue.isEmpty()) {
            Edge cur = queue.poll();
            if(distance[cur.vertex] < cur.distance) continue;

            for(Edge next : edges.get(cur.vertex)) {
                int nextVertex = next.vertex;
                long nextDist = cur.distance + next.distance;

                if(distance[nextVertex] > nextDist) {
                    distance[nextVertex] = nextDist;
                    queue.offer(new Edge(nextVertex, nextDist));
                }
            }
        }

        return distance;
    }

    static class Edge implements Comparable<Edge> {
        int vertex, state;
        long distance;

        public Edge(int vertex, long distance) {
            this.vertex = vertex;
            this.distance = distance;
        }

        public Edge(int vertex, long distance, int state) {
            this.vertex = vertex;
            this.distance = distance;
            this.state = state;
        }

        @Override
        public int compareTo(Edge o) {
            if(distance < o.distance) return -1;
            else 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());
        }
    }
}