[Boj_20183] 골목 대장 호석 - 효율성 2

📎 문제 링크

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

 

▸ 문제

소싯적 호석이는 골목 대장의 삶을 살았다. 호석이가 살던 마을은 N 개의 교차로와 M 개의 골목이 있었다. 교차로의 번호는 1번부터 N 번까지로 표현한다. 골목은 서로 다른 두 교차로를 양방향으로 이어주며 임의의 두 교차로를 잇는 골목은 최대 한 개만 존재한다. 분신술을 쓰는 호석이는 모든 골목에 자신의 분신을 두었고, 골목마다 통과하는 사람에게 수금할 것이다. 수금하는 요금은 골목마다 다를 수 있다.

당신은 A 번 교차로에서 B 번 교차로까지 C 원을 가지고 가려고 한다. 호석이의 횡포를 보며 짜증은 나지만, 분신술을 이겨낼 방법이 없어서 돈을 내고 가려고 한다. 하지만 이왕 지나갈 거면, 최소한의 수치심을 받고 싶다. 당신이 받는 수치심은 경로 상에서 가장 많이 낸 돈에 비례하기 때문에, 결국 갈 수 있는 다양한 방법들 중에서 최소한의 수치심을 받으려고 한다. 즉, 한 골목에서 내야 하는 최대 요금을 최소화하는 것이다.

예를 들어, 위의 그림과 같이 5개의 교차로와 5개의 골목이 있으며, 당신이 1번 교차로에서 3번 교차로로 가고 싶은 상황이라고 하자. 만약 10원을 들고 출발한다면 2가지 경로로 갈 수 있다. 1번 -> 2번 -> 3번 교차로로 이동하게 되면 총 10원이 필요하고 이 과정에서 최대 수금액을 5원이었고, 1번 -> 4번 -> 5번 -> 3번 교차로로 이동하게 되면 총 8원이 필요하며 최대 수금액은 6원이 된다. 최소한의 수치심을 얻는 경로는 최대 수금액이 5인 경로이다. 하지만 만약 8원밖에 없다면, 전자의 경로는 갈 수 없기 때문에 최대 수금액이 6원인 경로로 가야 하는 것이 최선이다.

당신은 앞선 예제를 통해서, 수치심을 줄이고 싶을 수록 같거나 더 많은 돈이 필요하고, 수치심을 더 받는 것을 감수하면 같거나 더 적은 돈이 필요하게 된다는 것을 알게 되었다. 마을의 지도와 골목마다 존재하는 호석이가 수금하는 금액을 안다면, 당신이 한 골목에서 내야하는 최대 요금의 최솟값을 계산하자. 만약 지금 가진 돈으로는 절대로 목표 지점을 갈 수 없다면 -1 을 출력하라.

 

▸ 입력

첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 수금액이 공백으로 구분되어 주어진다. 같은 교차로를 잇는 골목은 최대 한 번만 주어지며, 골목은 양방향이다.

 

▸ 출력

호석이가 지키고 있는 골목들을 통해서 시작 교차로에서 도착 교차로까지 C 원 이하로 가는 경로들 중에, 지나는 골목의 요금의 최댓값의 최솟값을 출력하라. 만약 갈 수 없다면 -1을 출력한다.

 

▸ 제한

1 ≤ N ≤ 100,000

1 ≤ M ≤ 500,000

1 ≤ C ≤ 1014

1 ≤ 골목 별 수금액 ≤ 109

1 ≤ A, B ≤ N, A ≠ B

골목이 잇는 교차로의 번호는 서로 다르다.

 

📍 문제 정보

• 🥇 문제 레벨 : 골드 2
• 🔔  문제 유형 : 그래프 이론, 이분 탐색, 최단 경로, 데이크스트라, 매개 변수 탐색
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

다익스트라만 알고리즘만으로도 해결할 수 있고, 다익스트라와 이분 탐색을 조합하여 해결할 수도 있다.

 

이 문제는 한 골목에서 내야 하는 최대 수금액의 최솟값을 구하는 문제이다.

특히, 수치심은 경로 상에서 가장 많이 낸 돈과 비례하므로, 이를 최소화하는 경로를 찾는 것이 목표다.

 

먼저, 다익스트라 알고리즘을 사용해서 문제를 해결해 보자.

 

다익스트라 알고리즘은 보통 최소 비용 경로를 찾는데 사용되지만, 이 문제에서는 경로 상에서 가장 큰 수치심을 최소화하는 경로를 찾아야 한다. 이를 위해 수치심의 최댓값이 작은 경로를 우선적으로 탐색할 수 있도록 정렬 기준을 설정하였다.

 

시작 교차로 a에서 출발하여 우선순위 큐를 사용해 탐색을 진행한다.

이때, 각 경로에서의 수치심은 현재까지의 최대 수치심과 새로 이동할 골목의 요금 중 큰 값으로 갱신한다.

모든 교차로에 대한 수치심의 최댓값은 dist 배열에 저장하며, 더 나은 수치심 경로가 발견되면 큐에 추가해 준다.

또한, 누적 요금이 가진 돈 c를 초과하면 해당 경로는 탐색하지 않는다.

 

탐색 중 도착 교차로 b에 도달하면, 해당 경로의 수치심 최댓값을 반환한다.

만약 우선순위 큐를 모두 탐색한 뒤에도 도착 교차로에 도착하지 못하면 -1을 출력한다.

 

 

 

두 번째로는 다익스트라와 이분 탐색을 조합하여 문제를 해결해 보자.

 

먼저, 이분 탐색을 진행하기 위해 수치심의 범위를 설정한다. (최소 수치심 = 1, 최대 수치심 = 1,000,000,000)

그다음, 중간값(mid)을 기준으로 한 골목에서 허용 가능한 최대 수치심을 설정하고, 다익스트라를 사용하여 mid 이하의 수치심으로만 시작 교차로에서 목표 교차로까지 이동 가능한지 탐색한다. 이 과정에서 수치심이 mid를 초과하는 골목은 탐색 대상에서 제외한다.

 

탐색 결과, 누적 비용이 가진 돈 c를 초과하는 경우, 현재 mid 값으로는 목표 교차로에 도달할 수 없음을 의미하므로 더 큰 수치심 값을 탐색한다.

반대로, 이동이 가능한 경우에는 더 작은 mid 값을 탐색하여 수치심의 최댓값을 줄인다.

 

이 과정을 반복하면서, 목표 교차로에 도달 가능한 최소 수치심의 최댓값을 찾는다.

 

다익스트라와 이분 탐색을 조합하여 문제를 해결할 때, 문제에 주어진 입력 값의 범위를 잘 확인하고, 이를 기반으로 탐색 범위를 적절하게 설정하는 것이 중요하다.

 

두 가지 풀이를 코드로 각각 작성해 보면 아래와 같다.

 

✔ 최종 코드 - 다익스트라

메모리 : 223584KB
시간 : 932ms

 

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

public class Main {
    static int n, m, a, b;
    static long c;
    static ArrayList<ArrayList<Pos>> list;
    static public class Pos implements Comparable<Pos> {
        int end; long dist; long shy;
        public Pos(int end, long dist) {
            this.end = end; this.dist = dist;
        }
        public Pos(int end, long dist, long shy) {
            this.end = end; this.dist = dist; this.shy = shy;
        }
        // 수치심이 작은 것을 기준으로 정렬
        @Override
        public int compareTo(Pos o) {
            return Long.compare(this.shy, o.shy);
        }
    }
    static final Long INF = Long.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // 교차로 개수
        m = Integer.parseInt(st.nextToken()); // 골목 개수
        a = Integer.parseInt(st.nextToken()); // 시작 교차로 번호
        b = Integer.parseInt(st.nextToken()); // 도착 교차로 번호
        c = Long.parseLong(st.nextToken()); // 가진 돈

        list = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }
        int u, v, w;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
            // 양방향 도로
            list.get(u).add(new Pos(v, w));
            list.get(v).add(new Pos(u, w));
        }

        System.out.println(dijkstra(a)); // 시작 교차로
    }

    private static long dijkstra(int a) {
        PriorityQueue<Pos> pq = new PriorityQueue<>();
        pq.offer(new Pos(a, 0, 0));
        long[] dist = new long[n+1]; // 가장 작은 수치심의 최댓값
        Arrays.fill(dist, INF);
        dist[a] = 0;

        while (!pq.isEmpty()) {
            Pos now = pq.poll();
			
            // 도착점
            if (now.end == b) return dist[b];
			
            // 이미 저장된 최적의 경로보다 더 큰 비용을 유발하는 경우
            // 현재 경로를 탐색 할 필요 없음
            // 즉, 현재 위치의 가장 작은 수치심의 최댓값을 구했으므로
            // now.shy 값이 더 크다면 탐색할 필요 X
            if (dist[now.end] < now.shy) continue;

            for (Pos next : list.get(now.end)) {
            	// 소지한 돈 보다 누적 지불 금액이 크다면 갈 수 없음
                if (now.dist + next.dist > c) continue;
            	// 경로에서 수치심 최댓값 갱신
                if (dist[next.end] > Math.max(dist[now.end], next.dist)) {
                    dist[next.end] = Math.max(dist[now.end], next.dist);
                    pq.offer(new Pos(next.end, now.dist + next.dist, dist[next.end]));
                }
            }
        }
        
        // 갈 수 없다면
        return -1;
    }
}

 

✔ 최종 코드 - 다익스트라 + 이분탐색

메모리 : 344488KB
시간 : 3844ms

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

public class Main {
    static int n, m, a, b;
    static long c;
    static ArrayList<ArrayList<Pos>> list;
    static public class Pos implements Comparable<Pos> {
        int end; long dist;
        public Pos(int end, long dist) {
            this.end = end; this.dist = dist;
        }
        @Override
        public int compareTo(Pos o) {
            return Long.compare(this.dist, o.dist);
        }
    }
    static final int INF = 1_000_000_007;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // 교차로 개수
        m = Integer.parseInt(st.nextToken()); // 골목 개수
        a = Integer.parseInt(st.nextToken()); // 시작 교차로 번호
        b = Integer.parseInt(st.nextToken()); // 도착 교차로 번호
        c = Long.parseLong(st.nextToken()); // 가진 돈

        list = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }
        int u, v, w;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
            // 양방향 도로
            list.get(u).add(new Pos(v, w));
            list.get(v).add(new Pos(u, w));
        }

        System.out.println(dijkstra(a));
    }

    private static long dijkstra(int a) {
        PriorityQueue<Pos> pq = new PriorityQueue<>();

        int start = 1; // 최소 수치심
        int end = 1_000_000_000; // 최대 수치심
        long ans = INF;
        while (start <= end) {
            // 한 골목에서 허용 가능한 수치심 최댓값
            // mid 이하의 수금액만 사용해 경로를 찾을 수 있는지 판단
            int mid = start + (end-start) / 2;
            long[] dist = new long[n+1];
            Arrays.fill(dist, 600_000_000_000_000L);
            pq.offer(new Pos(a, 0));
            dist[a] = 0;
            while (!pq.isEmpty()) {
                Pos now = pq.poll();
                // 이미 저장된 최적의 경로보다 더 큰 비용을 유발하는 경우
                // 현재 경로를 더 탐색 할 필요 없음
                if (dist[now.end] < now.dist) continue;
                for (Pos next : list.get(now.end)) {
                    // 골목의 수금액이 mid보다 크다면 패스
                    if (next.dist > mid) continue;
                    if (dist[next.end] > now.dist + next.dist) {
                        dist[next.end] = now.dist + next.dist;
                        pq.offer(new Pos(next.end, dist[next.end]));
                    }
                }
            }
            
            if (dist[b] > c) { // 가진 돈으로 이동 불가하다면 수치심 증가하여 탐색
                start = mid+1;
            } else { // 이동 가능하다면 더 작은 수치심 탐색
                ans = mid;
                end = mid-1;
            }
        }

        // 가능한 경로가 없다면 -1
        ans = ans == INF ? -1 : ans;
        return ans;
    }
}

 

다익스트라만으로도 풀 수 있는 문제였지만, 다익스트라와 이분 탐색을 조합해서도 풀 수 있는 문제라 새롭고 재밌었다.

해결 완료 ! 🔥