[백준][코틀린][13549] 숨바꼭질3

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

문제 풀이

1. 숨바꼭질1, 4 와 같이 BFS 로 풀 경우 오류가 발생한다. 각 시간 증가가 다르기 때문에 BFS + 가중치가 있는 그래프 알고리즘 이므로 다익스트라 알고리즘을 이용해야 한다.

2. Play 라는 Data Class 를 선언하고 time 에 따라 오름 차순으로 정렬될 수 있도록 Comparable 을 상속한다.

3. 우선 순위 Queue 를 이용하여 탐색한다.

3-1. 방문 배열을 선언한다.(visit)

3-2. 걷는 경우(현재 거리 +1, -1)와 순간이동하는 경우(현재 거리 * 2) 에 대해서 탐색한다.

3-3. distance 배열을 10만 1개의 크기로 선언하고 초기값을 Int.MAX_VALUE 로 설정한다.

3-4. nextTime 이 distance[nextPosition] 보다 작을 경우 distance 배열을 업데이트 한다.

4. distance[K] 를 결과로 출력한다.

코드

import java.io.*
import java.util.*

private val distance = IntArray(100001) { Int.MAX_VALUE }

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (N, K) = br.readLine().split(" ").map { it.toInt() }
    //bfs(N, K)
    dijkstra(N, K)
    println(distance[K])
}

private fun dijkstra(start: Int, target: Int) {
    val queue = PriorityQueue<Play>()
    val visit = BooleanArray(100001) { false }
    queue.add(Play(start, 0))
    distance[start] = 0

    while (queue.isNotEmpty()) {
        val (curPosition, curTime) = queue.poll()!!

        if (visit[curPosition]) continue

        visit[curPosition] = true

        if (curPosition == target) {
            break
        }

        for (i in 0..2) {
            val nextPosition = when (i) {
                0 -> curPosition - 1
                1 -> curPosition + 1
                else -> curPosition * 2
            }

            val nextTime = when (i) {
                0, 1 -> curTime + 1
                else -> curTime
            }

            if (nextPosition < 0 || nextPosition > 100000) continue

            //println("curPosition : $curPosition, curTime : $curTime, $nextPosition, $nextTime, ${distance[nextPosition]}")

            if (nextTime < distance[nextPosition]) {
                distance[nextPosition] = nextTime
            }

            queue.add(Play(nextPosition, distance[nextPosition]))
        }
    }
}

private data class Play(val position: Int, val time: Int) : Comparable<Play> {
    override fun compareTo(other: Play): Int {
        return time - other.time
    }
}