[백준, Java] 27281번, 운전병의 딜레마(다익스트라, 이분탐색)

문제 링크

27281번: 운전병의 딜레마

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

1. 운전병은 1번 구역에서 N번 구역에 T시간 이하로 도달해야 합니다.

2. 도로는 양방향이며, 불편도와 걸리는 시간이 존재합니다.

3. 시간의 값은 합, 불편도의 값은 최대 값입니다.

4. N번 구역에 도착할 수 있는 최소 불평도를 결과로 출력합니다.

5. 도로의 불편도는 시간을 늘린만큼 줄일 수 있습니다.

6. 도달할 수 있는 방법이 없으면 -1을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 이분탐색을 통해 불편도의 값을 탐색한 뒤 도착할 수 있는지 다익스트라를 통해 검증합니다.

 

3. 탐색해서 얻은 최소 불편도의 값을 결과로 출력합니다.

 

 

이분 탐색(불편도 탐색)

 

최대 불편도 탐색

 

도로의 정보 중 가장 큰 불편도의 값을 구합니다.

 

이후 이분 탐색을 통해서 최소 불편도를 찾는 과정을 진행합니다.

 

→ 이분 탐색 중 Parametric Search을 사용할 것입니다.

 

Parametric search - Wikipedia

 

다익스트라(불편도 검증)

 

다익스트라를 진행하기 전, 도로의 시간과 불편도의 관계에 대해서 정립하고 지나가야 합니다.

 

다익스트라를 진행하는 이유는 불편도를 검증하는 것으로써, 현재 불편도이하로 도로를 지나가야 합니다.

 

현재 불편도 : 4

 

{시간, 불편도}

 

도로 1 : {2, 3} : 불편도 4보다 이하이기 때문에 걸린 시간은 2

 

도로 2 : {2, 4} : 불편도 4보다 이하이기 때문에 걸린 시간은 2

 

도로 3 : {2, 5} : 불편도 4보다 크기 때문에 불편도 4로 만들기 위해서 시간을 1(5 - 4)만큼 올린 뒤에 이동할 수 있습니다.

※ "도로의 불편도는 시간을 늘린만큼 줄일 수 있습니다"을 이용한 것입니다.

 

점화식

 

위를 점화식으로 표현하면

 

시간 : 기존 시간 + Math.max(0, 도로 불편도 - 현재 불편도)

 

위 점화식을 토대로 각 도로마다 시간을 재계산하여 다익스트라를 진행합니다.

 

다익스트라를 진행해서 결국 T시간 안에 N번 구역에 도달하였을 때 해당 불편도는 1번에서 N번까지 도달할 수 있는 불편도입니다.

 

※예제입력 과정을 확인하시면 이해하시기 편하실 것입니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 4

 

M : 4

 

T : 6

 

 

 

 

2. 이분탐색을 통해 불편도의 값을 탐색한 뒤 도착할 수 있는지 다익스트라를 통해 검증합니다.

 

최대 불편도 : 4

 

Parametric Search 진행

 

Start : 0

 

End : 4

 

mid : (0 + 4) ÷ 2 = 2

 

불편도 2일 때 다익스트라 검증 시작

 

※ 불편도 2기준 점화식을 통해 도로 정보 변경

 

 

 

 

 

1 → 3 → 4 : 최단 시간 : 6 ≤ T(6)

 

불편도 2는 조건에 성립!

 

▶ End : 1

 

Parametric Search 진행

 

Start : 0

 

End : 1

 

mid : (0 + 1) ÷ 2 = 0

 

불편도 0일 때 다익스트라 검증 시작

 

※ 불편도 0기준 점화식을 통해 도로 정보 변경

4번 지역에 T(6) 안에 도달할 수 있는 경로가 없습니다.

 

불편도 0는 조건에 성립하지 않음!

 

▶ Start : 1

 

Parametric Search 진행

 

Start : 1

 

End : 1

 

mid : (1 + 1) ÷ 2 = 1

 

불편도 1일 때 다익스트라 검증 시작

 

 

4번 지역에 T(6) 안에 도달할 수 있는 경로가 없습니다.

 

불편도 1는 조건에 성립하지 않음!

 

▶ Start : 2

 

Parametric Search 종료

 

3. 탐색해서 얻은 최소 불편도의 값을 결과로 출력합니다.

 

탐색을 통해 얻은 최소 불편도 : 2

 

2 결과로 출력 합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 도로의 정보를 띄어쓰기 기준 저장합니다.
• search함수를 통해서 최소 불편도를 탐색합니다.
• 탐색을 통해 얻은 최소 불편도를 BufferedWriter 저장합니다.
• N번 지역에 도달하지 못하면 -1을 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 Parametric Search를 이용해서 불편도를 탐색합니다.
• bfs함수는 다익스트라와 점화식을 통한 도로의 재정의로 현재 불편도가 N번 지역에 T시간 안에 도달할 수 있는지 확인합니다.

결과코드

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


public class Main {
    //도로 정보 관련 클래스
    static class Road{
        //nxt : 연결된 구역
        //time : 시간
        //discomfort : 불편도
        int nxt, time, discomfort;
        Road(int nxt, int time, int discomfort){
            this.nxt = nxt;
            this.time = time;
            this.discomfort = discomfort;
        }
    }
    //PriorityQueue에 사용할 클래스
    static class Info implements Comparable<Info>{
        //idx : 현재 위치
        //time : 시간
        int idx;
        long time;
        Info(int idx, long time){
            this.idx = idx;
            this.time = time;
        }
        //시간 기준 오름차순 정렬
        @Override
        public int compareTo(Info o) {
            if(this.time >= o.time)
                return 1;
            return -1;
        }
    }
    //도로 정보 저장 List
    static List<List<Road>> roads = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());
        //도로 List 초기화
        for(int i=0;i<=N;i++){
            roads.add(new ArrayList<>());
        }
        int maxDiscomfort = 0;
        //도로 정보 저장
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            //최대 불편도 구하기
            maxDiscomfort = Math.max(maxDiscomfort, d);
            //양방향 도로 정보
            roads.get(a).add(new Road(b,t,d));
            roads.get(b).add(new Road(a,t,d));
        }
        //Parametric Search 진행
        int result = search(N, T, maxDiscomfort);
        //N번 구역에 도달하지 못할 때
        if(result == maxDiscomfort+1){
            bw.write("-1");
        }else{	//N번 구역에 도달할 때 BufferedWriter 저장
            bw.write(String.valueOf(result));
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //다익스트라를 이용하여 불편도 검증하는 함수
    static boolean bfs(int N, int mid, int T){
        //다익스트라를 위한 Priority Queue
        PriorityQueue<Info> pq = new PriorityQueue<>();
        //각 구역 최단 시간 정보 저장 Array
        long[] DP = new long[N+1];
        Arrays.fill(DP, Long.MAX_VALUE);
        DP[1] = 0L;
        pq.offer(new Info(1,0L));
        //다익스트라 진행
        while(!pq.isEmpty()){
            Info cur = pq.poll();
            //최단 시간이 아닐 때
            if(DP[cur.idx] < cur.time){
                continue;
            }
            //최단 시간으로 N번 구역 도달시
            if(cur.idx == N){
                return true;
            }
            //연결된 도로 탐색
            for(Road road : roads.get(cur.idx)){
                //점화식을 통해 도로 정보 재정의
                long nxtTime = cur.time + road.time + Math.max(0, road.discomfort - mid);
                //T시간을 벗어나는 이동일 경우
                if(nxtTime > T || DP[road.nxt] <= nxtTime){
                    continue;
                }
                DP[road.nxt] = nxtTime;
                pq.offer(new Info(road.nxt, nxtTime));
            }
        }
        //불편도 미성립!
        return false;
    }
    //Parametric Search을 통해서 불편도 탐색
    static int search(int N, int T, int maxDiscomfort){
        int start = 0;
        int end = maxDiscomfort;
        int mid;
        int result = maxDiscomfort + 1;
        //이분탐색 진행
        while(start <= end){
            mid = (start + end) / 2;
            //불편도 성립할 때
            if(bfs(N, mid, T)){
                end = mid - 1;
                result = Math.min(result, mid);
            }else{	//불편도 성립하지 않을 때
                start = mid+1;
            }
        }
        return result;
    }
}