13549번: 숨바꼭질 3 - Kotlin

13549번: 숨바꼭질 3

https://kr.freepik.com/free-photo/kids-having-fun-with-traditional-games_23670334.htm#query=%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88&position=10&from_view=keyword&track=sph

 

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

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

출력

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

나의 풀이

지문을 읽어보면 가장 빠른 시간을 구하라고 합니다. 그리고 다음 간선이 어딘지 알고 있습니다. 그렇다면 우리는 다익스트라로 풀어야 겠다고 생각할 수 있습니다.

항상 느끼는 거지만 문제를 보고 어떤 알고리즘으로 해결해야 할 것인지 아는 것이 문제를 해결하는 능력에서 가장 중요한 부분인것 같습니다.

 

다익스트라로 풀어야 하겠다고 생각만 했다면, 이 문제의 구현은 생각보다 어렵지 않습니다.

 

Kotlin

import java.util.*

data class Node(val index:Int, val distance:Int):Comparable<Node>{
    override fun compareTo(other:Node):Int =
        distance - other.distance
}

fun main() = with(System.`in`.bufferedReader()) {

    val (n, k) = readLine().split(" ").map { it.toInt() }

    dijkstra(n, k)
}

fun dijkstra(n: Int, k: Int) {
    val pq = PriorityQueue<Node>().apply { offer(Node(n, 0)) }
    val visited = BooleanArray(100001).apply { this[n] = true }

    while (pq.isNotEmpty()) {
        val (now, distance) = pq.poll()

        visited[now] = true

        if (now == k) {
            println(distance)
            break
        }

        if (now * 2 <= 100000 && !visited[now * 2]) {
            pq.offer(Node(now * 2, distance))
        }
        if (now + 1 <= 100000 && !visited[now + 1]) {
            pq.offer(Node(now + 1, distance + 1))
        }
        if (now - 1 >= 0 && !visited[now - 1]) {
            pq.offer(Node(now - 1, distance + 1))
        }
    }
}