[백준/BOJ] 9019번: DSLR

문제

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

9019번: DSLR

해설

bfs를 이용하는 문제이다.

숫자를 관리하는데 있어, 문자열이 아닌 int형으로 계산하였다.

bfs를 수행할 때 사요오디는 Queue에는 두가지 정보가 담기게 된다.

현재 숫자와 여태 진행된 명령어 두가지로 저장된다. 즉, Pair(num, command)가 담기게 된다.

초기값으로는 Pair(startNum, "")이 된다.

 

각 명령어마다 계산하는 방법을 보자.

D -> 현재 숫자에 * 2 % 10000을 한다.

S -> 현재 숫자 - 1을 한다. 이때 값이 음수가 되면 9999로 바꿔준다.

L -> 각 자릿수를 왼쪽으로 옮겨준다. (n * 10) % 10000 + n / 1000을 한 값이 된다.

R -> 각 자릿수를 오른쪽으로 옮겨준다. (n / 10) + (n % 10) * 1000을 한 값이 된다.

 

이 값들이 0 ~ 10000 사이의 범위를 넘지 않고, 아직 방문하지 않은 숫자라면 방문 여부 처리를 해준 후, 큐에 저장하여 bfs를 계속해서 수행해주면 된다.

코드

import java.util.*

private lateinit var visited: BooleanArray

fun main() = with(System.`in`.bufferedReader()) {
    val testCase = readLine().toInt()

    repeat(testCase) {
        visited = BooleanArray(10001)
        val (a, b) = readLine().split(" ").map { it.toInt() }

        val command = bfs(a, b)
        println(command)
    }
}

private fun bfs(start: Int, end: Int): String {
    val que: Queue<Pair<Int, String>> = LinkedList()
    que.add(Pair(start, ""))
    visited[start] = true

    while(que.isNotEmpty()) {
        val cur = que.poll()
        val curNum = cur.first
        val curCommand = cur.second

        if(curNum == end) return curCommand

        var commandD = commandD(curNum)
        if(isCheck(commandD)) {
            visited[commandD] = true
            que.add(Pair(commandD, curCommand + "D"))
        }

        val commandS = commandS(curNum)
        if(isCheck(commandS)) {
            visited[commandS] = true
            que.add(Pair(commandS, curCommand + "S"))
        }

        var commandL = commandL(curNum)
        if(isCheck(commandL)) {
            visited[commandL] = true
            que.add(Pair(commandL, curCommand + "L"))
        }

        var commandR = commandR(curNum)
        if(isCheck(commandR)) {
            visited[commandR] = true
            que.add(Pair(commandR, curCommand + "R"))
        }
    }

    return ""
}

private fun commandD(num: Int): Int {
    val n = num * 2 % 10000
    return n
}

private fun commandS(num: Int): Int {
    var n = num - 1
    if(n < 0) n = 9999
    return n
}

private fun commandL(num: Int): Int {
    return (num * 10) % 10000 + (num / 1000)
}

private fun commandR(num: Int): Int {
    return (num / 10) + (num % 10) * 1000
}

private fun isCheck(num: Int): Boolean = (num in 0 until 10000 && !visited[num])