백준 13549 [kotlin]

문제

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

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

입력

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

출력

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

풀이

deque를 이용해서 워프하는 경우를   deque에 앞에 넣고 그 외의 시간이 결려서 이동하는것은 뒤로 넣어서 가중치 차이를 구분하여 구했다. 

코드

import java.util.Deque
import java.util.LinkedList

fun main()
{
    val input = readLine()!!.split(" ").map{it.toInt()}
    val N = input[0]
    val K = input[1]
    val MAX = 100001
    val visited = IntArray(MAX,{MAX})
    visited[N] = 0
    val dq : Deque<Int> = LinkedList()
    dq.addFirst(N)

    while(dq.isNotEmpty())
    {
        val pd = dq.removeFirst()
        if(pd == K) {
            println(visited[pd])
            return
        }
        if(pd * 2 < MAX && visited[pd*2] == MAX){
            dq.addFirst(pd*2)
            visited[pd*2] = visited[pd]
        }
        if (pd+1 < MAX && visited[pd+1] == MAX){
            dq.addLast(pd+1)
            visited[pd+1] = visited[pd] + 1
        }
        if (pd-1 >= 0 && visited[pd-1] == MAX){
            dq.addLast(pd-1)
            visited[pd-1] = visited[pd] + 1
        }
    }

}