소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:
“이제 슬슬 비번 바꿀 때도 됐잖아”
“응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
“그럼 8179로 해”
“흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
“흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
“귀찮아”
그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.
첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.
각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.
- 에라토스테네스의 체로 소수 거르기
- 자릿수 마다 바꿔가면서 bfs 탐색
- 우선순위 큐 사용
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시간은 낭비했다...
우리 모두 실수를...조심합시다