[BOJ 골드4] DSLR Kotlin

문제

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

풀이

• 문제를 보자마자 BFS가 생각나서 구현하고 돌렸는데 시간초과가 났다. 보니까 L, R 처리를 스트링으로 바꿔서 좀 복잡하게 처리했는데 이부분에서 시간이 많이 걸린듯 하다.

코드

import java.util.*

fun main() = with(System.`in`.bufferedReader()){
    val n = readLine().toInt()
    for(i in 1..n){
        val (a,b) = readLine().split(" ").map{it.toInt()}
        val visit = BooleanArray(10000){false}
        val regist = Array(10000){""}
        bfs(a,b, visit, regist)
    }
}

fun bfs(start : Int, target : Int, visit : BooleanArray, regist : Array<String>){
    val q = LinkedList<Int>()
    q.add(start)
    visit[start] = true
    while(!q.isEmpty()){
        val current = q.poll()
        if(current==target){
            println(regist[target])
            return
        }
        val D = (current*2)%10000
        val S = if(current==0) 9999 else current-1
        val L = (current%1000) * 10 + current/1000
        val R = (current%10) * 1000 + current/10

        if(!visit[D]){
            q.add(D);
            visit[D]=true;
            regist[D]=regist[current] + "D";
        }

        if(!visit[S]){
            q.add(S);
            visit[S]=true;
            regist[S]=regist[current] + "S";
        }
        if(!visit[L]){
            q.add(L);
            visit[L]=true;
            regist[L]=regist[current] + "L";
        }
        if(!visit[R]){
            q.add(R);
            visit[R]=true;
            regist[R]=regist[current] + "R";
        }
    }
}