백준 1884 (고속도로) - java

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

1884번: 고속도로

 

문제

봄캠프 기간 동안 고속도로의 통행료가 급격하게 올라, 참가자들이 자칫 집으로 돌아가지 못할 수도 있는 위기에 봉착했다! 통행료가 인하되기 전까지는 여기 속초에서 원쌤과 함께 계속 프로그래밍 공부를 해야 할 수도 있는 상황인 것이다! 이 모든 것은 귀가시에 사용할 교통비를, 고속도로 통행료가 오르기 전에 계산해서 들고 왔기 때문이다.

다급해진 여러분은 정해진 예산을 가지고 집으로 돌아갈 수 있을지 알아보고, 갈 수 있다면 그에 필요한 최단 이동거리를 계산하려고 한다. 이를 해결하기 위한 프로그램을 작성하라.

 

첫 줄에 여러분이 준비해 둔 교통비 K가 주어진다. (0≤K≤10,000) 둘째 줄과 셋째 줄에는 각각 도시의 숫자 N과 도로의 숫자 R이 주어진다. (2≤N≤100, 1≤R≤10,000) 이후 R개의 줄에 각 도로의 정보가 주어지는데, 각 줄은 네 개의 숫자 s, d, l, t로 이루어져 있다. s는 도로의 출발 도시 번호이고, d는 도로의 도착 도시 번호이다. l은 도로의 길이이고, t는 도로의 통행료이다. (1≤s≤N, 1≤d≤N, 1≤l≤100, 0≤t≤100)

도시의 번호는 1번부터 N번까지 빠짐없이 붙어 있다. 이곳 속초는 1번 도시이고, 여러분의 집은 N번 도시에 있다. 각 도로는 일방통행로이다. 서로 다른 두 도로가 서로 같은 시작 도시와 서로 같은 도착 도시를 가질 수 있음에 유의하라.

 

유형 : 다익스트라 + 다이나믹 프로그래밍 + 다익스트라 최적화

 

접근 방식

• 로직을 찾더라도 최적화를 하지 못한다면 시간 초과를 맞보게 될것이다.
• 2개 이상의 변수를 고려해야 하는 다익스트라 문제이다.
  • 첫 번째는 당연히 거리이다. 거리가 짧은 최단 경로를 찾는 문제이다.
  • 두 번째는 금액이다. 각 도로마다 금액이 정해져 있기 때문에 정해진 금액 내에서 도착할 수 있어야 한다.
• 위 문제가 까다로운 이유는 다음 경우를 생각해보면 알 수 있다.
  • 나는 k금액으로 5의 거리로 다음 지점에 이동했어 !!!
  • 나는... k-5금액으로 10의 거리로 다음 지점에 이동했어
• 누가 정답일까? 
  • 알 수 없다. 그게 이 문제가 까다로운 이유이다. 2가지의 변수를 모두 고려해야 하기 때문이다.
• 접근
  • 간단하다. 기존의 dis 배열을 1차원이 아닌 2차원으로 설정하는 것이다.
    • dp[i][j] => i번째 지점까지 j의 금액으로 간 최소 거리
• 최적화
  • 위 문제가 개인적으로 정말 어렵다고 생각하는 이유는 최적화가 중요하기 때문이다. 최적화를 못하면 계속 시간 초과가 발생한다.
  • 다익스트라의 우선순위 큐를 갱신 하는 if 로직에서 갈린다....
• 시간 초과 코드

for(Node next : graph[cur.v]){

    if(cur.c < next.c)
        continue;

    if(dis[next.v][cur.c - next.c] > dis[cur.v][cur.c] + next.l) {
         dis[next.v][cur.c - next.c] = dis[cur.v][cur.c] + next.l;
         pq.add(new Node(next.v,dis[next.v][cur.c - next.c],cur.c - next.c));
    }
}

• 시간 통과 코드

for(Node next : graph[cur.v]){

    if(cur.c < next.c)
        continue;

    if(dis[next.v][cur.c + next.c] <= dis[cur.v][cur.c] + next.l) {
        continue;
    }

    dis[next.v][cur.c + next.c] = dis[cur.v][cur.c] + next.l;
    pq.add(new Node(next.v,dis[next.v][cur.c + next.c],cur.c + next.c));
}

 

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int n = 0;
    static int m = 0;

    static int k = 0;

    static ArrayList<Node>[] graph;

    static int result = -1;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        k = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(bf.readLine(), " ");
        n = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(bf.readLine(), " ");
        m = Integer.parseInt(st.nextToken());

        graph = new ArrayList[n+1];
        for(int i=1;i<=n;i++){
            graph[i] = new ArrayList<>();
        }

        for(int i=1;i<=m;i++){
            st = new StringTokenizer(bf.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int l = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());


            if(c > k)
                continue;

            graph[s].add(new Node(e,l,c));
        }


        search();
        bf.close();
    }

    static void search(){
        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> x.c - y.c
        );

        int[][] dis = new int[n+1][k+1];

        for(int i=1;i<=n;i++){
            for(int j=0;j<=k;j++){
                dis[i][j] = Integer.MAX_VALUE;
            }
        }

        dis[1][0] = 0;
        pq.add(new Node(1,0,0));

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

            if(cur.v == n){
                continue;
            }

            if(dis[cur.v][cur.c] < cur.l)
                continue;

            for(Node next : graph[cur.v]){

                if(cur.c + next.c > k)
                    continue;

                if(dis[next.v][cur.c + next.c] <= dis[cur.v][cur.c] + next.l) {
                    continue;
                }

                dis[next.v][cur.c + next.c] = dis[cur.v][cur.c] + next.l;
                pq.add(new Node(next.v,dis[next.v][cur.c + next.c],cur.c + next.c));
            }
        }


        result = dis[n][0];

        for(int i=1;i<=k;i++){
            result = Math.min(result,dis[n][i]);
        }

        if(result == Integer.MAX_VALUE)
            result = -1;

        System.out.println(result);
    }
}
class Node{
    int v;
    int l;
    int c;

    Node(int v,int l,int c){
        this.v = v;
        this.l = l;
        this.c = c;
    }
}