[백준] 소수 경로

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

 

fun main() = with(Scanner(System.`in`)) {
    val size = nextInt()
    val sosu = searchSosu()

    fun bfs(current : Int , end : Int) : Int {
        val queue = LinkedList<MyNumber>()
        queue.add(MyNumber(end = end, count = 0, current = current))
        val isVisited = Array<Boolean>(10001) { false }
        isVisited[current] = true

        while (queue.isNotEmpty()) {
            val current = queue.pop()
            if(current.current == current.end){
                return current.count
            }
            val cCurrent = getNumberArrays(current.current)

            for (i in 0 until 4) {
                val offset = if(i == 0) 1 else 0
                for (j in offset.. 9) {
                    val number = getNumber(i = i , j = j , cCurrent = cCurrent)
                    if(!sosu[number] || isVisited[number]){
                        continue
                    }
                    isVisited[number] = true
                    queue.add(MyNumber(current = number, end = current.end , count = current.count + 1))
                }
            }
        }
        return -1
    }
    for (i in 0 until size) {
        println(bfs(current = nextInt() , end = nextInt()).takeIf { it != -1 } ?: "Impossible")
    }
}

fun getNumber(i : Int, j : Int, cCurrent : Array<Int>) : Int{
    return when (i) {
        0 -> {
            (1000 * j) + (100 * cCurrent[1]) + (10 * cCurrent[2]) + (cCurrent[3])
        }

        1 -> {
            (1000 * cCurrent[0]) + (100 * j) + (10 * cCurrent[2]) + (cCurrent[3])
        }

        2 -> {
            (1000 * cCurrent[0]) + (100 * cCurrent[1]) + (10 * j) + (cCurrent[3])
        }

        3 -> {
            (1000 * cCurrent[0]) + (100 * cCurrent[1]) + (10 * cCurrent[2]) + (j)
        }
        else -> {
            0
        }
    }
}

fun getNumberArrays(input: Int): Array<Int> {
    val array = Array<Int>(4) { 0 }
    array[0] = input / 1000
    array[1] = (input % 1000) / 100
    array[2] = (input % 100) / 10
    array[3] = input % 10
    return array
}

data class MyNumber(val end: Int, val count: Int, val current: Int)

fun searchSosu(): Array<Boolean> {
    val limit = 10000
    val isPrime = Array(limit + 1) { true } // 기본적으로 모두 true로 초기화
    isPrime[0] = false
    isPrime[1] = false

    for (i in 2..limit) {
        if (isPrime[i]) {
            var multiple = i * 2
            while (multiple <= limit) {
                isPrime[multiple] = false
                multiple += i
            }
        }
    }
    return isPrime
}