[백준 1939 - Kotlin] 중량제한

문제링크

• Binary Search의 대상을 weight로 두고 BFS로 모든 섬을 순회하면서 source 섬에서 destination 섬까지 가는 경로가 있고, 검색하고자 하는 weight로 갈 수 있는 경로인지 확인하면 됩니다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.util.*

data class Bridge(val destination: Int, val weight: Int)

private lateinit var bufferedReader: BufferedReader
private lateinit var bufferedWriter: BufferedWriter
private lateinit var bridges: Array<MutableList<Bridge>>

fun main() {
    bufferedReader = System.`in`.bufferedReader()
    bufferedWriter = System.out.bufferedWriter()

    // 1. get n, m
    val (n, m) = bufferedReader
        .readLine()
        .split(" ")
        .map { it.toInt() }

    // 2. get bridge information
    bridges = Array(n + 1) { mutableListOf() }
    var maxWeight = 0
    repeat(m) {
        val (a, b, c) = bufferedReader
            .readLine()
            .split(" ")
            .map { it.toInt() }
        bridges[a].add(Bridge(b, c))
        bridges[b].add(Bridge(a, c))

        // 3. get max weight
        if (maxWeight < c) maxWeight = c
    }

    // 4. get factories
    val (factory1, factory2) = bufferedReader
        .readLine()
        .split(" ")
        .map { it.toInt() }


    // 5. possible weight binary search
    var start = 0
    var end = maxWeight

    while (start <= end) {
        val mid = (start + end) / 2
        if (isPossibleWeight(n, factory1, factory2, mid)) start = mid + 1
        else end = mid - 1
    }
    bufferedWriter.write("$end")

    bufferedReader.close()
    bufferedWriter.close()
}

fun isPossibleWeight(n: Int, source: Int, destination: Int, targetWeight: Int): Boolean {
    val queue: Queue<Int> = LinkedList()
    val visited = Array(n + 1) { false }
    queue.add(source)
    visited[source] = true

    while (queue.isNotEmpty()) {
        val currDestination = queue.poll()
        if (currDestination == destination) return true

        for (nextIsLand in bridges[currDestination]) {
            if (!visited[nextIsLand.destination] && nextIsLand.weight >= targetWeight) {
                queue.add(nextIsLand.destination)
                visited[nextIsLand.destination] = true
            }
        }
    }
    return false
}