[백준 1963번] [Kotlin] 소수 경로

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

1963번: 소수 경로

난이도 : 골드 4
태그 : 수학, 그래프 이론, 그래프 탐색, 정수론, 너비 우선 탐색, 소수 판정, 에라토스테네스의 체

 

 

설명

한 번에 한 글자씩 수를 바꿀 수 있으며, 바꾼 숫자는 소수여야 합니다.

목표 숫자로 바꾸는 최소 횟수를 출력하는 문제입니다.

 

너비 우선 탐색(BFS)을 사용해 '숨바꼭질' 문제와 같이 최단 경로(최소 횟수)를 찾는 문제입니다.

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

1697번: 숨바꼭질

 

 

한 글자씩 바꾸면서, 목표 숫자로 바꾸는 최소 횟수를 찾으면 됩니다.

다만, 목표 숫자 뿐 아니라 거쳐가는 숫자 역시 소수여만 하며,

매 BFS 탐색 시 마다 소수인지 판단하면 시간 초과가 발생할 수 있습니다.

 

 

에라토스테네스의 체

때문에 저는 에라토스테네스의 체를 통해 소수를 미리 구해줬습니다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

에라토스테네스의 체는 소수를 찾는 방법 중 하나로써, 소수의 배수를 미리 지워놓는 방법입니다.

소수 2의 배수는 4, 6, 8, 10 .. 등을 모두 지우고,

다음 소수 3의 배수 6, 9, 12, 15, 18 .. 을 모두 지우고,

4는 이미 지웠기에 넘어갑니다.

다음 소수 5의 배수 10, 15, 20, 25, 30 .. 을 모두 지우고,

6은 이미 지웠기에 넘어갑니다.

 

위 과정을 반복하여 지우지 않은 수를 탐색하면 효율적으로 소수를 찾을 수 있습니다.

 

 

 

소스코드

lateinit var isPrime: BooleanArray

fun main() = with(System.`in`.bufferedReader()) {
    isPrime = BooleanArray(10000) { true }

    for (i in 2..9999) {
        if (isPrime[i]) {
            for (j in i + i..9999 step i) {
                isPrime[j] = false
            }
        }
    }

    val sb = StringBuilder()

    repeat(readLine().toInt()) {
        val (start, end) = readLine().split(" ").map { it.toInt() }
        val shortestPath = findShortestPath(start, end)
        sb.appendLine(if (shortestPath == -1) "Impossible" else shortestPath)
    }

    print(sb)
}

fun findShortestPath(start: Int, end: Int): Int {
    if (start == end) return 0

    val visited = IntArray(10000) { -1 }
    visited[start] = 0

    val queue = ArrayDeque<Int>()
    queue.add(start)

    while (queue.isNotEmpty()) {
        val cur = queue.removeFirst()

        for (i in 0..<4) {
            for (j in 0..9) {
                val next = changeNumber(cur, i, j)

                if (next < 1000 || !isPrime[next] || visited[next] != -1) continue
                queue.add(next)
                visited[next] = visited[cur] + 1

                if (next == end) {
                    return visited[next]
                }
            }
        }
    }

    return -1
}

fun changeNumber(originNumber: Int, index: Int, targetNumber: Int): Int {
    val parsedNumber = originNumber.toString().toCharArray()
    parsedNumber[index] = targetNumber.digitToChar()
    return parsedNumber.joinToString("").toInt()
}

 

 

 

후기

BFS를 사용한 최소 횟수 찾기를 연습하기 좋은 문제 같네요.

다만 소수 찾기 - 에라토스테네스의 체를 사용해야 하는 테크닉이 조금 필요한 문제였습니다.