[백준 12763] - 지각하면 안 돼 Java

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

12763번: 지각하면 안 돼

문제를 요약하면 건물 N개가 있는데 1번 건물에서 출발해 N번까지 시간 내에 도달하면서 최저 비용 경로를 찾고, 그때의 비용을 구하면 된다.

풀이

먼저 가중치가 있는 그래프가 주어지기 때문에 다익스트라로 접근했다.

이 때, N번 건물까지 도달할 때 시간은 제한 시간 내에 도착만 하면 되고, 비용을 최소화해야 한다. 따라서 비용으로 먼저 정렬 후, 시간 순서대로 정렬했다.

static class Node implements Comparable<Node> {
    int next;
    long time, cost;

    public Node(int next, long time, long cost) {
        this.next = next;
        this.time = time;
        this.cost = cost;
    }

    @Override
    public int compareTo(Node o) {
        if(this.cost==o.cost){
            return Long.compare(this.time, o.time);
        }
        return Long.compare(this.cost,o.cost);
    }
}

탐색에서 이용할 노드 클래스는 위처럼 정의해 두고 다익스트라 알고리즘을 수행하면 최저 비용 경로 순으로 계속 탐색하게 되고, 도달할 때마다 제한 시간 내에 도착했는지 여부를 확인하면 된다.

 

방문노드 처리가 핵심인데, 방문여부만 처리하게 되면

같은 노드를 지나더라도 더 비싼 비용으로 비용 시간이 초과하지 않는 경우를 계산할 수 없다.

 

이런 문제를 해결해주기 위해 방문 비용, 방문 시간 두 가지의 방문 배열을 관리하여

둘 중 하나라도 갱신되는 경우에 탐색을 수행하도록 설계했다.

long[] visitCost = new long[N + 1];
long[] timeCost = new long[N + 1];
Arrays.fill(visitCost, Long.MAX_VALUE);
Arrays.fill(timeCost, Long.MAX_VALUE);

visitCost는 비용, timeCost는 도착시간.

 

다익스트라는 아주 일반적인 방법으로 구현했다.

PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(1, 0, 0));

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

    if (visitCost[now.next] < now.cost && timeCost[now.next] < now.time) {
        continue;
    }

     visitCost[now.next] = now.cost;
     timeCost[now.next] = now.time;

     if(now.next==N) {
         if(now.time<=T) {
             System.out.println(now.cost);
             return ;
         }
     }
    for (Node node : map.get(now.next)) {
        if((timeCost[node.next]>now.time+node.time||visitCost[node.next]>now.cost+node.cost)&&now.cost+node.cost<=M) {
            pq.add(new Node(node.next, node.time + now.time, node.cost + now.cost));
        }
    }
}

정답 코드

package 백준_2024년.스터디_5wnck;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class problem3 {
    static class Node implements Comparable<Node> {
        int next;
        long time, cost;

        public Node(int next, long time, long cost) {
            this.next = next;
            this.time = time;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            if(this.cost==o.cost){
                return Long.compare(this.time, o.time);
            }
            return Long.compare(this.cost,o.cost);
        }
    }
    static HashMap<Integer, PriorityQueue<Node>> map = new HashMap<>();
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        for(int i= 1;i<=N;i++) {
            map.put(i, new PriorityQueue<>());
        }

        int L = Integer.parseInt(br.readLine());
        for(int i= 0;i<L;i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            map.get(start).add(new Node(end, time, cost));
            map.get(end).add(new Node(start, time, cost));
        }
        long[] visitCost = new long[N + 1];
        long[] timeCost = new long[N + 1];
        Arrays.fill(visitCost, Long.MAX_VALUE);
        Arrays.fill(timeCost, Long.MAX_VALUE);

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(1, 0, 0));

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

            if (visitCost[now.next] < now.cost && timeCost[now.next] < now.time) {
                continue;
            }

             visitCost[now.next] = now.cost;
             timeCost[now.next] = now.time;

             if(now.next==N) {
                 if(now.time<=T) {
                     System.out.println(now.cost);
                     return ;
                 }
             }
            for (Node node : map.get(now.next)) {
                if((timeCost[node.next]>now.time+node.time||visitCost[node.next]>now.cost+node.cost)&&now.cost+node.cost<=M) {
                    pq.add(new Node(node.next, node.time + now.time, node.cost + now.cost));
                }
            }
        }

        System.out.println(-1);

    }
}