[백준] 16118번 달빛여우 (Java)

문제

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

16118번: 달빛 여우

---

풀이

모든 정점에 대한 최단 경로를 탐색하는 다익스트라 알고리즘 문제

 

가장 중요한 고려사항은 늑대의 경우 홀수/짝수번째로 건넜을 경우를 각각 저장해 줄 수 있어야 함!

속도가 /2가 될 수 있으므로 소수점 방지를 위해 처음 입력 받을 시 weight에 *2 를 곱하여 저장!

 

다익스트라 알고리즘은 PriorityQueue를 사용하여 구현

코드

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

public class Main {
    static class Edge implements Comparable<Edge>{
        int end, weight, dir;
        public Edge(int end, int weight) {
            this.end = end;
            this.weight = weight;
        }
        public Edge(int end, int weight, int dir) {
            this.end = end;
            this.weight = weight;
            this.dir = dir;
        }
        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.weight, o.weight);
        }
    }
    static int N, M;
    static List<Edge>[] graph;
    static int[] disFox;
    static int[][] disWolf; // 1: 홀,짝 / 2: 거리
    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];
        for(int i =0 ; i < N ; i++){
            graph[i] = new ArrayList<>();
        }

        disFox = new int[N];
        disWolf = new int[2][N];

        for(int i =0 ; i < M ; i++){
            st = new StringTokenizer(br.readLine());
            int to = Integer.parseInt(st.nextToken())-1;
            int from = Integer.parseInt(st.nextToken())-1;
            int dis = Integer.parseInt(st.nextToken());

            graph[to].add(new Edge(from, dis*2));   // 정수의 나눗셈 결과를 위해 *2
            graph[from].add(new Edge(to, dis*2));
        }

        Arrays.fill(disFox, Integer.MAX_VALUE);
        Arrays.fill(disWolf[0], Integer.MAX_VALUE);
        Arrays.fill(disWolf[1], Integer.MAX_VALUE);

        findFoxPath();
        findWolfPath();

        int cnt = 0;
        for(int i =0 ; i < N ; i++){
            if(disFox[i] < Integer.min(disWolf[0][i], disWolf[1][i])) cnt++;
        }
        System.out.println(cnt);
    }


    private static void findWolfPath() {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(0, 0, 0));

        disWolf[0][0] = 0;

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

            if(disWolf[cur.dir][cur.end] < cur.weight) continue;    // 이미 비교 값보다 작은 경우

            for(Edge nEdge : graph[cur.end]){
                int nNode = nEdge.end;
                int nWeight = cur.weight;
                int nDir = 0;

                if(cur.dir == 0){   // 현재 홀수번째로 건넜다면
                    nWeight += nEdge.weight / 2;    // 속도 두배
                    nDir = 1;       // 다음 짝수
                } else{     // 현재 짝수번째로 건넜다면
                    nWeight += nEdge.weight * 2;    // 속도 1/2배
                    nDir = 0;   // 다음 홀수
                }

                if(disWolf[nDir][nNode] > nWeight){
                    disWolf[nDir][nNode] = nWeight;
                    pq.add(new Edge(nNode, nWeight, nDir));
                }
            }
        }
    }

    // 기본 다익스트라 알고리즘
    private static void findFoxPath() {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(0, 0));

        disFox[0] = 0;

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

            if(disFox[cur.end] < cur.weight) continue;

            for(Edge nEdge : graph[cur.end]){
                int nNode = nEdge.end;
                int nWeight = cur.weight + nEdge.weight;

                if(disFox[nNode] > nWeight){
                    disFox[nNode] = nWeight;
                    pq.add(new Edge(nNode, nWeight));
                }
            }
        }
    }
}