[백준][코틀린][9019] DSLR

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

9019번: DSLR

문제 풀이

1. A, B 숫자 입력을 받는다.

2. A == B 가 될때까지 BFS 를 이용하여 탐색한다.

3. (현재 숫자, 수행된 명령어)를 저장하는 Queue를 선언한다.

4. visit 배열을 선언하고 크기를 10,001 로 잡는다. 숫자가 이미 사용되었는 지 유무를 확인하는 배열로 사용한다.

5. D 명령어는 문제 따라 nextNum * 2 % 10,000 의 값으로 처리한다.

6. S 명령어는 nextNum 이 0일때에는 9999 를 그외에는 nextNum - 1 값으로 처리 한다.

7. L 명령어는 제일 앞자리가 끝으로 가고 나머지 숫자들이 왼쪽으로 한 칸 이동 하는 규칙을 파악하여 다음 수식으로 결과를 얻는다.

(num % 1000) * 10 + (num / 1000)

8. R 명령어 역시 아래의 수식으로 결과를 얻는다.

(num / 10) + (num % 10) * 1000

코드

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

private val result = StringBuilder()

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var T = br.readLine().toInt()

    while (T > 0) {
        val (A, B) = br.readLine().split(" ").map { it.toInt() }
        bfs(A, B)
        T--
    }

    println(result.toString())
}

private fun bfs(A: Int, B: Int) {
    val queue = LinkedList<Pair<Int, String>>() // 현재 숫자, 현재까지 수행한 명령어
    queue.add(Pair(A, ""))
    val visit = BooleanArray(10001) { false } // 이미 나온 숫자인지를 확인한다.
    visit[A] = true

    while (queue.isNotEmpty()) {
        val (cNum, cCmd) = queue.pop()

        if (cNum == B) {
            result.append("$cCmd\n")
            break
        }

        // 0:D, 1:S, 2:L, 3:R
        for (i in 0..3) {
            val newNum = changeNumber(cNum, i)

            // 이미 탐색한 숫자.
            if (visit[newNum]) continue

            visit[newNum] = true
            queue.add(Pair(newNum, cCmd + getCmd(i)))
        }
    }
}

private fun getCmd(idx: Int): String {
    return when(idx) {
        0 -> "D"
        1 -> "S"
        2 -> "L"
        else -> "R"
    }
}

private fun changeNumber(num: Int, cmd: Int): Int {
    return when (cmd) {
        //D
        0 -> (num * 2) % 10000
        //S
        1-> if (num == 0) 9999 else num - 1
        //L
        2-> (num % 1000) * 10 + (num / 1000)
        //R
        else -> (num / 10) + (num % 10) * 1000
    }
}