백준 10776 (제국) - java

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

10776번: 제국

 

문제

사회에 불만이 많은 지용이는 미적분학 교과서를 적당히 찢어서, 한 사람이 충분히 탈 만한 두께 K의 뗏목을 만들었다.

지용이는 이제 A 항구에서 출발해서 무인도 B에 자신의 제국을 건설하기 위해 멀고 먼 여행을 떠날 계획이다. (1 ≤ A, B ≤ N, A ≠ B)

바다에는 N개의 섬이 있고 M개의 바닷길이 있으며, 바닷길 외의 길로는 갈 수가 없으며 지용이는 A에서 B로 가는 동안 섬들을 거쳐가면서 항해할 계획이다.

각 바닷길은 지나가는 데 걸리는 시간 ti, 뗏목을 깎아내리는 정도 hi (cm) 를 가지고 있으며, 만약에 도착하기 전에 뗏목이 0cm 이하의 두께를 가지게 된다면 - 달리 말해서 경로 상의 hi의 합이 K 이상이 된다면, 수영을 못하는 지용이의 목숨을 보장하지 못할수도 있다(!)

지용이는 가장 빠른 시간 내에 A에서 B 지점까지 안전하게 가기를 원한다. 지용이를 도와 그러한 길의 길이를 출력해주자.

 

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

 

접근 방식

• dis 배열을 2차원으로 설정한다.
  • dis[i][k] : i번째 노드를 k의 뗏목 cm으로 갈때 최소 시간

전체 코드

package Implementation_BruteForce;

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

public class BOJ_10776_제국 {

    static int k,n,m,s,e;

    static ArrayList<Node>[] graph;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        k = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        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(br.readLine()," ");
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());

            graph[v1].add(new Node(v2,t,h));
            graph[v2].add(new Node(v1,t,h));
        }

        st = new StringTokenizer(br.readLine()," ");
        s = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        search();

        br.close();
    }

    static void search(){

        int result = -1;

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

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

        dis[s][k] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> x.t - y.t
        );

        pq.add(new Node(s,0,k));

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

            if(cur.v == e){
                result = cur.t;
                break;
            }

            if(dis[cur.v][cur.h] < cur.t)
                continue;

            for(Node next : graph[cur.v]){
                int nextH = cur.h - next.h;

                if(nextH <= 0)
                    continue;

                if(dis[next.v][nextH] > cur.t + next.t){
                    dis[next.v][nextH] = cur.t + next.t;
                    pq.add(new Node(next.v,dis[next.v][nextH],nextH));

                    for(int tmpH = nextH - 1 ; tmpH >= 1 ; tmpH--){
                        if(dis[next.v][tmpH] > dis[next.v][nextH]){
                            dis[next.v][tmpH] = dis[next.v][nextH];
                        }else{
                            break;
                        }
                    }
                }
            }
        }

        System.out.println(result);

    }

    static class Node{
        int v;
        int t;
        int h;

        Node(int v,int t,int h){
            this.v = v;
            this.t = t;
            this.h = h;
        }
    }
}