백준 - 숨바꼭질3(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/13549

 

[문제 설명]

현재 위치에서 -1, +1, *2를 할 수 있다.

목적지에 도착하는데 걸리는 최소 시간은?

 

[접근 방법]

동적프로그래밍으로 생각하여, 점화식을 계속 유도하다가 제한 시간이 지나서 다른 사람들 답지에서 힌트를 봤다.

BFS로 접근하는 것을 보고 아차 싶어서 바로 스스로 구현해서 풀었다. 난이도 자체는 크게 있지 않은 문제인데, 숨바꼭질 1,2였나?

비슷한 유형의 문제가 동적프로그래밍을 사용한 문제여서 사고가 거기에 갇혔었다.

동적프로그래밍에 너무 약한듯하다.

 

암튼 이 문제는 결국, 현재 위치에서 +1 -1 *2를 하는 경우를 찾으면 된다.

여기서 의아한 사람도 있을 거다. 현재 위치에서 3가지 경우의 수가 나오면 결국 O(3^n)의 시간복잡도가 되는 게 아니냐??

나도 여기서 이 방법을 선택하는 것을 포기했었다.

그러나, 제대로 생각해보면 이 문제의 조건은 가장 가까운 거리를 찾는 문제이다.

따라서, 후에 방문했던 요소가 나와도 거리가 더 가깝지 않으면 탐색하지 않는다.

결과적으로 시간복잡도는 BFS의 시간복잡도인 O(V + E)가 되므로 여유가 있다.

+ 도착지가 출발지보다 작거나 같으면 단순히 -1로 가는 수밖에 없으므로 도착지 - 현재위치가 정답이다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.LinkedList

class Node(val position: Int, val currentCost: Int)

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (x, n) = br.readLine().split(" ").map { it.toInt() }
    if (n <= x) {
        println(x - n)
        return
    }

    val mapSize = x.coerceAtLeast(n) * 2 + 1
    println(getMinCostToDestination(x, n, mapSize))
}

private fun getMinCostToDestination(start: Int, destination: Int, mapSize: Int): Int {
    val map = IntArray(mapSize + 1) { Int.MAX_VALUE }
    val queue = LinkedList<Node>()

    queue.offer(Node(start, 0))
    while (queue.isNotEmpty()) {
        val cNode = queue.poll()

        if (cNode.position + 1 <= mapSize) {
            if (map[cNode.position + 1] > cNode.currentCost + 1) {
                map[cNode.position + 1] = cNode.currentCost + 1
                queue.offer(Node(cNode.position + 1, cNode.currentCost + 1))
            }
        }

        if (0 <= cNode.position - 1) {
            if (map[cNode.position - 1] > cNode.currentCost + 1) {
                map[cNode.position - 1] = cNode.currentCost + 1
                queue.offer(Node(cNode.position - 1, cNode.currentCost + 1))
            }
        }

        if (cNode.position * 2 <= mapSize) {
            if (map[cNode.position * 2] > cNode.currentCost) {
                map[cNode.position * 2] = cNode.currentCost
                queue.offer(Node(cNode.position * 2, cNode.currentCost))
            }
        }
    }

    return map[destination]
}