[백준] 소수 경로 - 골드 4 (Kotlin)

문제

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

“이제 슬슬 비번 바꿀 때도 됐잖아”
“응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
“그럼 8179로 해”
“흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
“흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
“귀찮아”
그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

입력

첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.

출력

각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.

풀이

1. 에라토스테네스의 체로 소수 거르기
2. 자릿수 마다 바꿔가면서 bfs 탐색
3. 우선순위 큐 사용

소스 코드

import java.util.*

fun main() {
    val solution = Solution()

    solution.solution()
}

const val INF = 123456789

class Solution {

    fun solution() {
        val T = readLine()!!.toInt()

        val prime = Array(10000) { 1 }

        for (i in 2 until 10000) {
            if (prime[i] == 0) continue

            for (j in 2 * i until 10000 step i) {
                prime[j] = 0
            }
        }

        repeat(T) {
            var visit = Array(10000) { false }
            val (start, end) = readLine()!!.split(' ')
            val queue = PriorityQueue<Node>()
            var result = -1

            queue.offer(Node(start.toInt(), 0))

            while (queue.isNotEmpty()) {
                val node = queue.poll()

                if (prime[node.num] == 0) continue
                if (visit[node.num]) continue
                if (node.num == end.toInt()) {
                    result = node.count
                    break
                }

                visit[node.num] = true

//                println("${node.num} is prime, count = ${node.count}")

                 for (index in 0 until 4) {
                    val now = node.num.toString()[index]

                     for (time in 0 until 10) {
                        if (index == 0 && time == 0) continue
                        if (time == now.toString().toInt()) continue

                        val next = buildString {
                            if (index == 0) append(time) else append(node.num.toString()[0])
                            if (index == 1) append(time) else append(node.num.toString()[1])
                            if (index == 2) append(time) else append(node.num.toString()[2])
                            if (index == 3) append(time) else append(node.num.toString()[3])
                        }

                        queue.offer(Node(next.toInt(), node.count + 1))
                    }
                }
            }
            println(if (result != -1) result else "Impossible")
        }
    }
}

data class Node(
    val num: Int,
    val count: Int
) : Comparable<Node> {
    override fun compareTo(other: Node): Int {
        return when {
            count > other.count -> 1
            count < other.count -> -1
            count == other.count -> 0
            else -> INF
        }
    }
}

요약 및 정리

예제 1033 -> 8179 를 예로 들면
2033, 3033, 4033, ..., 1039 까지 자릿수마다 숫자를 변경하며 큐에 삽입한다. 변경을 한 번 해줄 때 마다 count 를 하나씩 늘려준다.
큐에서 꺼낼 때는 해당 값이 소수가 아니면 pass, 이미 방문했다면 pass, 결과(8179)와 일치하면 종료한다.
문제는 생각보다 간단했는데
val next = buildString {
if (index == 0) append(time) else append(start[0])
if (index == 1) append(time) else append(start[1])
if (index == 2) append(time) else append(start[2])
if (index == 3) append(time) else append(start[3])
}
이 부분을 start 로 잡아놓고 있어서 방문처리 여부에 따라 무한 반복 or 처음 한 싸이클만 하고 끝나길래 왜 그런가 고민하느라 2시간은 낭비했다...
우리 모두 실수를...조심합시다