[백준][코틀린][1963] 소수 경로

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

1963번: 소수 경로

문제 풀이

1. 주어진 입력을 BFS 를 통해서 완전 탐색 한다.

2. 주어진 숫자는 4자리이므로 천의 자리부터 일의 자리까지 탐색 한다.

3. 0 ~ 9 까지의 숫자를 바꿀 수 있으므로 각 경우에 대해서 탐색한다.

4. 이때 천의 자리가 0으로 올 수 없으므로 조건을 추가 한다.

5. 이전에 탐색한 숫자를 확인하기 위한 방문 배열 visit 를 선언한다.

6. 탐색하는 숫자가 현재 숫자와 같은 지 확인 한다.

7. 변경된 숫자가 소수인지 확인 한다.

8. 목표 숫자에 도착했을 때 변환한 count 값을 출력한다.

코드1 - 에라토스테네스의 체를 몰랐을 때

import java.io.*
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var T = br.readLine().toInt()
    val result = StringBuilder()

    while (T > 0) {
        val (start, target) = br.readLine().split(" ").map { it.toString() }
        val count = bfs(start, target)
        result.append("${if (count == -1) "Impossible" else count}\n")
        T--
    }

    println(result.toString())
}

private fun bfs(start: String, target: String): Int {
    val queue = LinkedList<Prime>()
    val visit = BooleanArray(10000) { false }
    queue.add(Prime(start, 0))
    visit[start.toInt()] = true

    while (queue.isNotEmpty()) {
        val current = queue.pop()

        if (current.number == target) return current.count

        for (i in 0..3) {
            for (j in 0..9) {
                val num = current.number[i] - '0'
                val nextNumber = when (i) {
                    0 -> "$j${current.number.substring(1, current.number.length)}"
                    1 -> "${current.number.substring(0, 1)}$j${current.number.substring(2, current.number.length)}"
                    2 -> "${current.number.substring(0, 2)}$j${current.number.substring(3, current.number.length)}"
                    else -> "${current.number.substring(0, current.number.length - 1)}$j"
                }

                // 4자리 숫자가 아니다.
                if (nextNumber.toInt() / 1000 == 0) continue
                // 현재 숫자와 같다.
                if (j == num) continue
                // 이미 탐색한 숫자.
                if (visit[nextNumber.toInt()]) continue
                // 소수가 아니다.
                if (!isPrime(nextNumber.toInt())) continue

                visit[nextNumber.toInt()] = true
                queue.add(Prime(nextNumber, current.count + 1))
            }
        }
    }

    return -1
}

private fun isPrime(number: Int): Boolean {
    for (i in 2 until number) {
        if (number % i == 0) return false
    }

    return true
}

private data class Prime(val number: String, val count: Int)

코드2 - 에라토스테네스의 체 알고리즘 + BFS + StringBuilder.setCharAt

import java.io.*
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var T = br.readLine().toInt()

    //에라토스테네스의 체를 이용하여 소수를 구한다.
    val prime = BooleanArray(10000) { true }
    val sqrt = Math.sqrt(9999.0).toInt()

    for (i in 2..sqrt) {
        // 소수가 아니다.
        if (!prime[i]) continue

        //소수인 숫자의 배수를 탐색하여 primeCheck 에서 제거한다.
        var j = 2

        while (i * j <= 9999) {
            if (prime[i * j]) prime[i * j] = false
            j++
        }
    }

    val result = StringBuilder()

    while (T > 0) {
        val (start, target) = br.readLine().split(" ").map { it.toInt() }
        val count = bfs(start, target, prime)
        result.append("${if (count == -1) "Impossible" else count}\n")
        T--
    }

    println(result.toString())
}

private fun bfs(start: Int, target: Int, prime: BooleanArray): Int {
    val queue = LinkedList<Pair<Int, Int>>()
    queue.add(Pair(start, 0))
    val visit = BooleanArray(10000) { false }
    visit[start] = true

    while (queue.isNotEmpty()) {
        val current = queue.pop()

        if (current.first == target) return current.second

        for (i in 0..3) {
            for (j in 0..9) {
                // 천의 자리 숫자는 0으로 될 수 없다.
                if (i == 0 && j == 0) continue

                // 숫자 변경
                val newNumber = getNumber(current.first, i, j)

                //소수인지 확인
                if (!prime[newNumber]) continue
                //이미 탐색한 숫자인 지 확인
                if (visit[newNumber]) continue

                visit[newNumber] = true
                queue.add(Pair(newNumber, current.second + 1))
            }
        }
    }

    return -1
}

private fun getNumber(num: Int, index: Int, target: Int): Int {
    val sb = StringBuilder()
    sb.append(num.toString())
    sb.setCharAt(index,  target.digitToChar())
    return sb.toString().toInt()
}