백준 20168 골목 대장 호석 - 기능성 Kotlin (다익스트라 + 이분 탐색)

문제 출처 : https://www.acmicpc.net/problem/20168

20168번: 골목 대장 호석 - 기능성

문제

소싯적 호석이는 골목 대장의 삶을 살았다. 호석이가 살던 마을은 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 ≤ 10
• 1 ≤ M ≤ N × (N-1) / 2
• 1 ≤ C ≤ 10,000
• 1 ≤ 골목 별 수금액 ≤ 1,000
• 1 ≤ A, B ≤ N, A ≠ B
• 골목이 잇는 교차로의 번호는 서로 다르다.

알고리즘 분류

• 그래프 이론
• 브루트포스 알고리즘
• 데이크스트라
• 백트래킹

풀이

2022.05.12 - [알고리즘 문제 풀이/백준] - 백준 20182 골목 대장 호석 - 효율성 1 Kotlin (다익스트라 + 이분 탐색)

2022.05.14 - [알고리즘 문제 풀이/백준] - 백준 20183 골목 대장 호석 - 효율성 2 Kotlin (다익스트라 + 이분 탐색)

 

다익스트라 + 이분 탐색 문제이다.

호석님은 어찌 이런 야무진 문제들을 잘 내시는지

너무 좋다.

bfs + 이분 탐색도 아니고 다익스트라 + 이분 탐색이라니.

본인은 처음에 다익스트라 + 이분 탐색으로 풀었다가 어 다익스트라 필요 없겠다 싶어서 그냥 bfs로 바꿔서 제출했는데 통과하길래 괜찮은 줄 알았다.

결론부터 말하자면 현재 이 문제는 bfs + 이분 탐색, 다익스트라 + 이분 탐색 둘 다 통과한다.

아니 이 기능성 문제는 이분 탐색 안 해도 통과한다.

본인은 효율성 문제까지 고려해서 이분 탐색을 사용하였다.

우선 풀이부터 얘기하고 그럼에도 bfs+이분 탐색이 아닌 다익스트라 + 이분 탐색으로 풀어야 하는 이유를 설명하겠다.

이분 탐색을 이용하지 않은 풀이에는 해당하지 않는다.

 

우선 이분 탐색에서 탐색할 mid값은 골목의 요금의 최댓값의 최솟값, 즉 답을 mid로 두고, s와 e를 조정하면서 최적의 mid를 찾는다.

답의 최솟값은 1, 최댓값은 1000으로 s =1, e=1000

이제 이분 탐색으로 mid값이 정답 후보로 들어갈 수 있는지 다익스트라로 확인하고, 정답 후보로 들어갈 수 있다면 mid를 줄여서 더 작은 값도 가능한지 확인한다.

본인은 처음에 이 확인하는 로직을 bfs로 구현하였는데, 다음 탐색을 스킵하기 위한 조건으로

visited로 방문 체크,

if(nextSumCost > c || nextMaxCost > search) continue

search(=mid)값 보다 현재 루트에서 가장 큰 비용이 더 큰 경우, 현재 루트의 비용 합이 c보다 큰 경우를 조건으로 걸어주고,

현재 루트가 무사히 목적지에 도착한다면 true를 반환 (현재 mid값은 정답 후보로 들어갈 수 있다는 의미)했다.

하지만 우린 가능한 가장 적은 비용의 간선만을 이용해야 하며, 가장 적은 비용의 간선들을 이용한 루트에서 이 비용들 중 최댓값이 mid여야 했다. 즉, 목적지에 도달하기 위해 사용한 간선들의 비용이 가능한 작은 비용의 간선들의 집합이어야 했다.

bfs라면 가장 작은 간선을 우선적으로 탐색하지 않고 그냥 먼저 들어오는 간선을 우선적으로 타기 때문에, 목적지에 도착하는 루트가 있다고 하더라도 이 루트에서 사용한 간선들이 가장 작은 비용들의 집합임을 보장하지 않는다.

따라서 이를 보장하기 위해 PriorityQueue를 이용하여 가장 작은 간선을 우선적으로 탐색하게끔 해주어야 하는 것이다.

그냥 queue로 풀었다면 언젠가 이 문제에 데이터가 추가되면 오답 처리 될 수 있다..!  

이러한 문제점은 현재 골목 대장 호석 - 효용성 2번 문제를 제출하면 확인할 수 있다.

코드

import java.util.*
val br = System.`in`.bufferedReader()

fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

data class Node(
    val num: Int,
    val cost: Int,
    val sumCost: Int,
    val maxCost: Int
)
lateinit var edge: Array<ArrayList<Pair<Int,Int>>>

fun dijkstra(a: Int,b: Int,c: Int, search: Int, visited: BooleanArray) : Boolean{
    val q = PriorityQueue<Node>{ a,b ->
        when{
            a.cost < b.cost -> -1
            a.cost == b.cost -> 0
            else -> 1
        }
    }
    q.add(Node(a,0,0,0))
    visited[a] = true
    while(q.isNotEmpty()){
        val cur = q.poll()
        for(next in edge[cur.num]){
            if(visited[next.first]) continue
            val nextSumCost = cur.sumCost + next.second
            val nextMaxCost = cur.maxCost.coerceAtLeast(next.second)
            if(nextSumCost > c || nextMaxCost > search) continue
            if(next.first == b) return true
            q.add(Node(next.first, next.second, nextSumCost, nextMaxCost))
            visited[next.first] = true
        }
    }
    return false
}

fun main() = with(System.out.bufferedWriter()){
    //input
    val (n,m,a,b,c) = getIntList()
    edge = Array(n+1){ ArrayList() }
    repeat(m){
        val (from, to, cost ) = getIntList()
        edge[from].add(Pair(to,cost))
        edge[to].add(Pair(from,cost))
    }
    //solve
    var s = 1
    var e = 1000
    var mid = 0
    var answer = Int.MAX_VALUE
    while(s<=e){
        //가능하다면 mid를 줄여보기
        mid = (s+e)/2
        if(dijkstra(a,b,c,mid, BooleanArray(n+1))){
            answer = answer.coerceAtMost(mid)
            e = mid - 1
        }
        else{
            s = mid + 1
        }
    }
    //output
    if(answer==Int.MAX_VALUE) write("-1")
    else write("$answer")

    close()
}