[백준] 16118번 : 달빛 여우

 

 

16118번: 달빛 여우

---

[다익스트라]

오랜만에 다익스트라 알고리즘 문제를 풀어볼까 해서 여유롭게 푸는가 했으나 너무 안일하게 생각했던 문제. 여우는 문제없이 최단거리를 구할 수 있겠는데.... 늑대는 속도가 x2배 일 수도, 0.5배 일 수도 있으므로 조금 고민해보지 않으면 쉽지 않은 문제인 것 같다. 도대체 어떻게 접근해야할지 떠오르질 않아 질문 게시판을 보다가 아 이거구나 하는 질문을 찾았다. 링크는 하단에 공유하도록 한다.

 

먼저, 다익스트라는 2개가 있어야 한다. 여우에 대한 다익스트라, 늑대에 대한 다익스트라. 여우에 대한 다익스트라는 일반적인 다익스트라이므로 패스하도록 하고, 늑대에 대해 살펴보자.

 

늑대는 각 정점에 대하여 2번 방문할 수 있다. 바로 짝수번째로 도착할 때와 홀수번째로 도착할 때이다. 그러므로 나는 거리에 대한 배열을 여우꺼 1차원 배열, 늑대꺼 2차원 배열을 준비했다. 그리고 늑대는 자신이 다음에 방문할 정점을 짝수번째로 방문하는지, 홀수번째로 방문하는지에 대한 정보를 지니고 있어야한다.

 

int[ ] fox = new int[4001];

int[][] wolf = new int[4001][2];

 

이제 입력을 받을 차례인데, 입력을 받을 때 가중치(거리)를 받을 때는 * 2해서 입력받자. 이유는 정수로 표현해야하기 때문에, 0.5배 할 때 값이 손실되는 것을 방지하기 위함이다. 실제로 2배해서 넣지 않으면 틀렸다고 나온다. 

# Code </>

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

public class Main {

    static class Edge implements Comparable<Edge>{
        int tg, d, rest;
        public Edge(int target, int dist){
            tg = target;
            d = dist;
        }
        public Edge(int target, int dist, int r){
            this(target, dist);
            rest = r;
        }

        @Override
        public int compareTo(Edge o) {
            return d - o.d;
        }
    }
    static int n, m;
    
    static final int INF = 2000000000;
    static List<Edge>[] list = new ArrayList[4001];
    
    static int[][] wolf = new int[4001][2];
    static int[] fox = new int[4001];

    //rest == 1? 짝수번째로 도착, rest == 0? 홀수번째로 도착
    static void Dijkstra_wolf(){
        Queue<Edge> pq = new PriorityQueue<>();

        wolf[1][0] = 0;
        pq.add(new Edge(1, 0, 0));

        while(!pq.isEmpty()){
            Edge e = pq.poll();
            int cur = e.tg;
            int dist = e.d;
            int rest = e.rest;

            if(wolf[cur][rest] < dist) continue;

            for(Edge nE : list[cur]){
                int next = nE.tg;
                int nDist = dist;
                int nRest = -1;

                if(rest == 1){
                    nDist += nE.d * 2;
                    nRest = 0;
                }
                else{
                    nDist += nE.d / 2;
                    nRest = 1;
                }

                if(wolf[next][nRest] > nDist){
                    wolf[next][nRest] = nDist;
                    pq.add(new Edge(next, nDist, nRest));
                }
            }
        }
    }

    static void Dijkstra_fox(){

        Queue<Edge> pq = new PriorityQueue<>();
        fox[1] = 0;

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

        while(!pq.isEmpty()){
            Edge e = pq.poll();
            int cur = e.tg;
            int dist = e.d;

            if(fox[cur] < dist) continue;

            for(Edge ne:list[cur]){
                int next = ne.tg;
                int nDist = dist + ne.d;

                if(fox[next] > nDist){
                    fox[next] = nDist;

                    pq.add(new Edge(next, nDist));
                }
            }
        }
    }

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

        for(int i=1; i<=n; i++){
            list[i] = new ArrayList<>();
            fox[i] = INF;
            Arrays.fill(wolf[i], INF);
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());

            int h = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            list[h].add(new Edge(t, w * 2));
            list[t].add(new Edge(h, w * 2));
        }
        
        Dijkstra_fox();
        Dijkstra_wolf();

        int cnt = 0;
        for(int i=1; i<=n; i++)
            if(fox[i] < Math.min(wolf[i][1], wolf[i][0])) cnt++;

        System.out.println(cnt);
    }
}

# Reference

www.acmicpc.net/board/view/28797