[알고리즘] 숨바꼭질 3 (백준 13549번)

13549번: 숨바꼭질 3

 처음엔 BFS인 줄 알았는데 자세히 보니 이동하는 위치에 따라서 이동시간이 다르다. 이 말은 곧 간선마다의 가중치가 다르다는 뜻이므로 다익스트라를 이용해야 한다.

 

Solution

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

import java.util.*
import kotlin.collections.ArrayList

var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))

var N = 0
var K = 0
val INF = 100001
var dist = IntArray(INF, {INF})

fun solution() {

    var strtok = StringTokenizer(br.readLine())
    N = strtok.nextToken().toInt()
    K = strtok.nextToken().toInt()

    dist[N] = 0

    dijkstra()

    bw.write(dist[K].toString())
}

fun dijkstra()
{
    var queue = PriorityQueue<Node>(kotlin.Comparator { o1, o2 -> o1.distance - o2.distance })
    queue.offer(Node(N, 0))
    var visited = BooleanArray(INF)

    while(!queue.isEmpty())
    {
        var now = queue.poll()

        if(visited[now.num])
            continue
        visited[now.num] = true

        if(now.num == K)
            break

        //1. X + 1 (시간 : 1초)
        var next = now.num + 1

        if(next in 0..100000)
        {
            if(dist[next] > dist[now.num] + 1)
            {
                dist[next] = dist[now.num] + 1
                queue.offer(Node(next, dist[next]))
            }
        }

        //2. X - 1 (시간 : 1초)
        next = now.num - 1
        if(next in 0..100000)
        {
            if(dist[next] > dist[now.num] + 1)
            {
                dist[next] = dist[now.num] + 1
                queue.offer(Node(next, dist[next]))
            }
        }

        //3. X * 2 (시간 : 0초)
        next = now.num * 2
        if(next in 0..100000)
        {
            if(dist[next] > dist[now.num])
            {
                dist[next] = dist[now.num]
                queue.offer(Node(next, dist[next]))
            }
        }
    }
}

data class Node(var num : Int, var distance : Int)


fun main() {
    solution()
    br.close()
    bw.close()
}

 특별할 것 없이 다익스트라를 그대로 적용하고 X + 1, X - 1일 때는 가중치를 1로 잡고, X * 2일 때는 0으로 잡으면 된다.