[백준 1939 - Kotlin] 중량제한
14123 단어 BFSbinary_searchkotlinBFS
- 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
}
Author And Source
이 문제에 관하여([백준 1939 - Kotlin] 중량제한), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kldaji/백준-1939-Kotlin-중량제한저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)