[JAVA] 백준 20007 - 떡 돌리기

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

성현이가 출발점에서 한 정점씩 왕복할 때, 모든 정점을 왕복하는데에 몇일이 소요되는지 구하는 문제이다.

먼저 다익스트라로 각 정점까지의 최단 거리를 구한 후 만약 도달하지 못하는 정점이 있으면 -1을 반환하고 종료했다.

그리고 왕복거리로 설정하기 위해 각 최단 거리를 2배 해준 뒤 하루 최대 이동거리를 초과할 경우에도 -1을 반환하고 종료했다.

마지막으로 최단 거리 배열을 정렬한 뒤 최대 이동거리를 몇번 채울 수 있는지 구한 후 반환했다.

 

다익스트라를 함수로 빼서 사용해봤는데 훨씬 편하다.

자주 이용해야겠다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] info = getArray(br.readLine());
        int nodeCount = info[0];
        int roadCount = info[1];
        int maxWalk = info[2];
        int startNode = info[3];

        int[] dist = new int[nodeCount];
        Arrays.fill(dist, Integer.MAX_VALUE);
        List<List<P20007>> list = new ArrayList<>();
        for (int i = 0; i < nodeCount; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < roadCount; i++) {
            int[] road = getArray(br.readLine());
            list.get(road[0]).add(new P20007(road[1], road[2]));
            list.get(road[1]).add(new P20007(road[0], road[2]));
        }

        dijkstra(dist,startNode,list);
        for (int i = 0; i < nodeCount; i++) {
           if(dist[i]==Integer.MAX_VALUE){
               System.out.println(-1);
               return;
           } 
           dist[i] = 2 * dist[i];
           if(dist[i]>maxWalk){
               System.out.println(-1);
               return;
           }
        }
        Arrays.sort(dist);
        int count = 1;
        int limit = maxWalk;
        for (int i = 0; i < nodeCount; i++) {
            int temp = dist[i];
            if(limit - temp < 0){
                limit = maxWalk;
                i--;
                count++;
            }else{
                limit -= temp;
            }
        }
        System.out.println(count);
    }

    static void dijkstra(int[] dist, int startNode, List<List<P20007>> list) {
        PriorityQueue<P20007> pq = new PriorityQueue<>();
        dist[startNode] = 0;
        pq.offer(new P20007(startNode));
        while (!pq.isEmpty()) {
            P20007 poll = pq.poll();
            int value = poll.to;
            int weight = poll.weight;
            if (dist[value] < weight) continue;
            List<P20007> vList = list.get(value);
            for (int i = 0; i < vList.size(); i++) {
                P20007 road = vList.get(i);
                int to = road.to;
                int cost = road.weight;
                if (dist[to] > weight + cost) {
                    P20007 offer = new P20007(to);
                    offer.weight = weight + cost;
                    dist[to] = weight + cost;
                    pq.offer(offer);
                }
            }
        }
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class P20007 implements Comparable<P20007> {
    int to;
    int weight = 0;

    P20007(int t) {
        this.to = t;
    }

    P20007(int t, int weight) {
        this.to = t;
        this.weight = weight;
    }

    @Override
    public int compareTo(P20007 o) {
        return this.weight - o.weight;
    }
}