[BOJ] 1939번 : 중량제한

문제 보기

소스

kotlin

import kotlin.math.max

var n = 0
var m = 0
var start = 0
var end = 0
var result = 0
lateinit var graph: Array<ArrayList<Info>>
lateinit var visit: BooleanArray
lateinit var factory: Pair<Int, Int>

fun main() {
    init()
    binarySearch()
}

fun binarySearch() {
    while (start <= end) {
        val mid = (start + end) / 2
        visit = BooleanArray(n + 1)
        if (dfs(factory.first, mid)) {
            start = mid + 1
            result = mid
        } else {
            end = mid - 1
        }
    }

    println(result)
}

fun dfs(cur: Int, limit: Int): Boolean {
    if (visit[cur]) return false
    visit[cur] = true
    if (cur == factory.second) return true

    for (island in graph[cur]) {
        val (next, weight) = island.dest to island.weight
        if (weight >= limit) {
            if (dfs(next, limit)){
                return true
            }
        }
    }

    return false
}

fun init() {
    val br = System.`in`.bufferedReader()
    val firstLine = br.readLine().split(" ")
    n = firstLine[0].toInt()
    m = firstLine[1].toInt()
    graph = Array(n + 1) { ArrayList() }
    for (i in 0 until m) {
        val (a, b, c) = br.readLine().split(" ").map { it.toInt()}
        graph[a].add(Info(b, c))
        graph[b].add(Info(a, c))
        end = max(end, c)
    }
    val lastLine = br.readLine().split(" ")
    factory = lastLine[0].toInt() to lastLine[1].toInt()
}

data class Info(val dest: Int, val weight: Int)

BFS/DFS와 이분탐색을 함께 적용해서 풀어야하는 문제이다. 아직 BFS/DFS 문제에 익숙하지 않다보니 시간도 많이 소요되고 결국 다른 사람의 코드를 봐야했다. BFS/DFS 관련 문제를 많이 풀어보고 다시 이 문제를 풀어야겠다.