[백준/코틀린] 9019번: DSLR

링크

9019번: DSLR

풀이

0부터 9999까지를 숫자를 그래프의 정점으로 보고,
각 숫자에서 DSLR 연산으로 이동할 수 있는 상태를 그래프의 간선으로 본다면,
시작 숫자에서 목표 숫자로 가는 최단 경로를 구하는 BFS 문제로 볼 수 있습니다.

BFS를 통해 a에서 b까지의 최단거리와 그때의 경로를 구합니다.

코드

fun d(n: Int) = n * 2 % 10000
fun s(n: Int) = (n + 9999) % 10000
fun l(n: Int) = (n % 1000) * 10 + (n / 1000)
fun r(n: Int) = (n % 10) * 1000 + (n / 10)
fun commands(n: Int) = listOf(
    d(n) to 'D',
    s(n) to 'S',
    l(n) to 'L',
    r(n) to 'R',
)

fun bfs(start: Int, target: Int) {
    val queue = ArrayDeque<Pair<Int, String>>()
    val visited = BooleanArray(10000)

    visited[start] = true
    queue.addLast(start to "")
    while (queue.isNotEmpty()) {
        val (current, path) = queue.removeFirst()

        if (current == target) return println(path)
        commands(current).forEach { (next, symbol) ->
            if (!visited[next]) {
                visited[next] = true
                queue.addLast(next to path + symbol)
            }
        }
    }
}

fun main() = repeat(readln().toInt()) {
    val (a, b) = readln().split(" ").map { it.toInt() }

    bfs(a, b)
}