BOJ 9019_DSLR

문제

풀이

package solve_9019

import java.util.*


private val orders = arrayOf("D", "S", "L", "R")


fun main() = with(System.`in`.bufferedReader()) {

    repeat(readLine().toInt()) {
        val st = StringTokenizer(readLine())
        val a = st.nextToken().toInt()
        val b = st.nextToken().toInt()

        bfs(a,b)
    }

}


fun bfs(now: Int, target: Int){
    val queue: Queue<Resister> = LinkedList()
    val visited = BooleanArray(10001)
    queue.add(Resister(now, StringBuilder()))

    while (queue.isNotEmpty()) {
        val cur = queue.poll()
        for (order in orders) {
            var newNum = cur.num
            when (order) {
                "D" -> {
                    newNum = cur.num * 2
                    if (newNum > 9999) {
                        newNum %= 10000
                    }
                }
                "S" -> {
                    newNum = cur.num
                    if (newNum == 0) {
                        newNum = 10000
                    }
                    newNum -= 1
                }
                "L" -> {
                    val temp = cur.num / 1000
                    newNum = cur.num % 1000 * 10 + temp
                }
                "R" -> {
                    val temp = cur.num % 10
                    newNum = cur.num /10 + temp * 1000
                }
            }
            val sb = StringBuilder(cur.nowOrder.toString())
            sb.append(order)
            if(newNum == target){
                println(sb)
                queue.clear()
                return
            }
            if(visited[newNum].not()){
                queue.add(Resister(newNum, sb))
                visited[newNum] = true
            }
        }
    }
}

private data class Resister(val num: Int, val nowOrder: StringBuilder)

사용 알고리즘

bfs를 통해 탐색을 진행했다.
문제를 분석하고 코드를 작성하는 것에는 오래걸리지 않았지만 제출하고 보니 런타임에러라는 결과나 나타났다.

• 메모리 초과 1
  처음에는 bfs를 탐색하던 도중 target을 발견하면 그대로 return 해버리고 넘어갔다. 이렇게 되니 queue에 데이터가 남아있어도 그대로 유지하고 다음 테스트케이스를 탐색하는 것이 문제가 되는것인가 생각했다. target을 찾았을때 queue를 clear 시켜주어보았다.

• 메모리 초과 2
  여전히 메모리 초과가 발생하였다. 찾아보니 별도의 방문처리를 두지 않아 같은 숫자에 대해서도 Resiter를 생성하고 queue에 삽입하게 되는것이 문제일 것이라 생각했다. visited를 두어 한번 입력된 수에 대해서는 큐에 삽입하지 않았다.

• 인덱스 에러
  visited의 인덱스를 현재 숫자에 대한 값으로 두었는데 제출하고 보니 인덱스에러가 발생했다. 원인은 "S"의 경우였다. newNum을 cur.num - 1로 바로 두고 넘어갔었는데 이경우 num이 0으로 들어오게 되면 -1이 되어 에러가 발생하는 것이었다. 계산순서를 바꿔주어 해결할 수 있었다.