[백준/코틀린] 1697번: 숨바꼭질

링크

1697번: 숨바꼭질

풀이

세 가지 연산(-1, +1, *2)을 이용해 그래프를 탐색합니다.
최단 거리를 구해야 하므로 BFS를 사용합니다.

코드

val visited = BooleanArray(100001)
val mul = listOf(1, 1, 2)
val add = listOf(-1, 1, 0)

fun bfs(start: Int, target: Int) {
    val queue = ArrayDeque<Pair<Int, Int>>()

    visited[start] = true
    queue.addLast(start to 0)
    while (queue.isNotEmpty()) {
        val (current, depth) = queue.removeFirst()

        if (current == target) return println(depth)
        repeat(3) {
            val next = mul[it] * current + add[it]

            if (next in 0..100000 && !visited[next]) {
                visited[next] = true
                queue.addLast(next to depth + 1)
            }
        }
    }
}

fun main() {
    val (n, k) = readln().split(" ").map { it.toInt() }

    bfs(n, k)
}