백준 1939 중량제한

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

N개의 섬이 있고 섬과 섬 사이에 중량 제한이 있는 다리가 존재할 수 있다. 공장이 있는 두 섬 사이를 이동할 수 있는 중량의 최댓값을 구하는 문제.

예를 들어

위와 같은 상황에서 공장이 1번 위치와 5번 위치에 있다고 가정하면, 빨간색 경로로 최대 4의 중량을 이동시킬 수 있다.

먼저, 입력에서 섬 개수인 N은 1에서 10,000까지 이므로 섬의 연결정보는 이차원 배열이 아닌 연결 리스트 기반으로 작성하기로 하였다.
(이차원 배열을 사용하면 10000x10000 배열을 사용해야 하므로 메모리가 부족할 수 있다 생각하였다.)

위 구조를 바탕으로 연결 리스트를 구상해 보면 위와 같다.

1 - (2, 3) 는 1번 섬이 2번 섬과 중량 3의 다리로 연결되었다는 의미이다.

이제 본격적으로 알고리즘을 설계해보자.

1. 섬과 섬 사이의 중량을 입력받아 연결 리스트를 채우고 최소, 최대 중량을 구한다.

2. 최소 중량과 최대 중량 사이에서 이분탐색을 시행해 반복적으로 중간값에 해당하는 중량을 BFS를 통해 직접 시작 지점에서 도착 지점으로 보내 보며 이동 가능여부를 찾는다.

3. 이분탐색을 통해 구한 최대 중량을 출력한다.

위 과정을 구현한 코드는 다음과 같다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val (N,M) = readLine().split(' ').map{it.toInt()}

    val bridges = Array(N+1){LinkedList<Pair<Int,Int>>()}
    var minWeight = Int.MAX_VALUE
    var maxWeight = Int.MIN_VALUE
    for(i in 1..M){
        val (A,B,C) = readLine().split(' ').map{it.toInt()}
        if(C < minWeight) minWeight = C
        if(C > maxWeight) maxWeight = C
        bridges[A].add(Pair(B,C))
        bridges[B].add(Pair(A,C))
    }
    val (fac1, fac2) = readLine().split(' ').map{it.toInt()}
    var mid: Int

    while(minWeight <= maxWeight){
        mid = (minWeight + maxWeight) / 2

        if(canArrive(bridges, fac1, fac2, mid))
            minWeight = mid + 1
        else
            maxWeight = mid - 1
    }
    print(maxWeight)
}

fun canArrive(bridges: Array<LinkedList<Pair<Int,Int>>>, start: Int, end: Int, weight: Int): Boolean{
    val queue: Queue<Int> = LinkedList()
    val visited = BooleanArray(bridges.size){false}
    queue.offer(start)

    while(queue.isNotEmpty()){
        val next = queue.poll()
        if(next == end)
            return true

        for(n in bridges[next]){
            if(!visited[n.first] && weight <= n.second){
                visited[n.first] = true
                queue.offer(n.first)
            }
        }
    }

    return false
}

canArrive함수는 start 섬부터 end 섬까지 weight의 무게를 이동시킬 수 있는지 검사하는 함수입니다.

섬에서 섬으로 이동할 때 weight가 다리 중량보다 같거나 적으면 이동하도록 하였습니다.