[백준] 숨바꼭질 3 (13549)(kotlin)

문제 설명

백준 13549번 문제 링크

입력 및 출력

» 입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

» 출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입출력(테스트케이스)

입력	출력
5 17	2

문제 힌트

수빈이가 5-10-9-18-17 순으로 가면 2초만에 동생을 찾을 수 있다.

문제 풀이1

import java.util.*
import kotlin.math.max
import kotlin.math.min

var arr = intArrayOf()
var max = 0
class Point(val x: Int, val count: Int)

fun main() = with(System.`in`.bufferedReader()) {
    val (N, K) = readLine().split(" ").map { it.toInt() }
    max = max(N, K) * 2 + 1
    arr = IntArray(max) { Int.MAX_VALUE }
ß
    bfs(N, K)
    println(arr[K])
}

fun bfs(start: Int, dest: Int) {
    val q = LinkedList<Point>()
    q.add(Point(start, 0))

    while (q.isNotEmpty()) {
        val now = q.poll()
        arr[now.x] = min(arr[now.x], now.count)

        if (now.x == dest) break

        if (now.x * 2 <= dest + 1 && arr[now.x * 2] == Int.MAX_VALUE) {
            q.add(Point(now.x * 2, now.count))
        }

        if (now.x + 1 < max && arr[now.x + 1] == Int.MAX_VALUE) {
            q.add(Point(now.x + 1, now.count + 1))
        }

        if (now.x - 1 >= 0 && arr[now.x - 1] == Int.MAX_VALUE) {
            q.add(Point(now.x - 1, now.count + 1))
        }
    }
}