문제 설명

D, S, L, R 이라는 네가지 연산이 존재함.
초깃값 A를 B로 바꾸기위한 최소한의 연산(횟수가 아니라 일련의 스트링)을 찾는 것임. 만약 가능한 방법이 여러개면 그 중 하나를 출력.

접근

A를 B로 바꾸기 위해 dp를 적용할 수 있는지 생각해봤음, 하지만 문제를 보면 알겠지만 연산을 하면서 숫자가 0~9999를 사이클 돌기 때문에 끝이 없음.

어차피 가능한 숫자는 10000개이므로 그리 크지 않아서 BFS로 A에서 B까지 찾아보기로 함. 또한, 이미 등장한 숫자는 BFS의 특징을 따라 그 방법이 최소한의 이동값임. 그러므로 큐에 추가할지 안할지 이미 등장한 여부로 구분한다.

첫 풀이

map을 활용해서 해당 숫자를 만들기 위한 연산과정 스트링을 저장함. (지금와서 생각해보니 그냥 스트링 배열 사용해도 됐었을듯)

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

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    repeat(br.readLine().toInt()) {
        val (A, B) = br.readLine().split(" ").map { it.toInt() }
        val minMoveMap = HashMap<Int, String>()
        val q = LinkedList<Int>()
        q.add(A)
        minMoveMap[A] = ""
        while (q.isNotEmpty()) {
            val curN = q.poll()
            var remainN = curN
            val d1 = remainN / 1000
            remainN -= d1 * 1000
            val d2 = remainN / 100
            remainN -= d2 * 100
            val d3 = remainN / 10
            remainN -= d3 * 10
            val d4 = remainN

            val dResult = (curN * 2) % 10000
            if (minMoveMap[dResult] == null) {
                q.add(dResult)
                minMoveMap[dResult] = minMoveMap[curN] + 'D'
                if (dResult == B) break
            }

            val sResult = if (curN == 0) {
                9999
            } else {
                curN - 1
            }
            if (minMoveMap[sResult] == null) {
                q.add(sResult)
                minMoveMap[sResult] = minMoveMap[curN] + 'S'
                if (sResult == B) break
            }

            val lResult = (((d2 * 10) + d3) * 10 + d4) * 10 + d1
            if (minMoveMap[lResult] == null) {
                q.add(lResult)
                minMoveMap[lResult] = minMoveMap[curN] + 'L'
                if (lResult == B) break
            }


            val rResult = (((d4 * 10) + d1) * 10 + d2) * 10 + d3
            if (minMoveMap[rResult] == null) {
                q.add(rResult)
                minMoveMap[rResult] = minMoveMap[curN] + 'R'
                if (rResult == B) break
            }
        }
        println(minMoveMap[B])
    }
}

통과는 했으나 시간이 처참했음. 다른사람들의 풀이를 찾아본 결과, 방문여부는 따로 배열을 만들고 이걸 활용해서 이미 존재하는지 여부를 판단했음. 불리언값 비교가 스트링 비교보다 시간복잡도 면에서 저렴한다는 것에서 차이가 컸던 듯하다.

개선 코드

기존 코드를 조금 수정해서 불리언 값비교로 수정했다.

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

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    repeat(br.readLine().toInt()) {
        val (A, B) = br.readLine().split(" ").map { it.toInt() }
        val isVisited = BooleanArray(10000)
        val q = LinkedList<Pair<Int, String>>()
        q.add(A to "")
        isVisited[A] = true
        while (q.isNotEmpty()) {
            val (curN, curString) = q.poll()
            var remainN = curN
            val d1 = remainN / 1000
            remainN -= d1 * 1000
            val d2 = remainN / 100
            remainN -= d2 * 100
            val d3 = remainN / 10
            remainN -= d3 * 10
            val d4 = remainN

            val dResult = (curN * 2) % 10000
            if (!isVisited[dResult]) {
                q.add(dResult to curString + 'D')
                isVisited[dResult] = true
                if (dResult == B) {
                    println(curString + 'D')
                    break
                }
            }

            val sResult = if (curN == 0) {
                9999
            } else {
                curN - 1
            }
            if (!isVisited[sResult]) {
                q.add(sResult to curString + 'S')
                isVisited[sResult] = true
                if (sResult == B) {
                    println(curString + 'S')
                    break
                }
            }

            val lResult = (((d2 * 10) + d3) * 10 + d4) * 10 + d1
            if (!isVisited[lResult]) {
                q.add(lResult to curString + 'L')
                isVisited[lResult] = true
                if (lResult == B) {
                    println(curString + 'L')
                    break
                }
            }


            val rResult = (((d4 * 10) + d1) * 10 + d2) * 10 + d3
            if (!isVisited[rResult]) {
                q.add(rResult to curString + 'R')
                isVisited[rResult] = true
                if (rResult == B) {
                    println(curString + 'R')
                    break
                }
            }
        }
    }
}

시간이 거의 3배 줄어들었다.

배운점

스트링 비교 시간을 간과하지 말자