[Joco][백준/BOJ] 1525 번: 퍼즐 (Kotlin)

[문제]

1525번: 퍼즐

[깃허브]

GitHub - Dev-Joco/algorithm-kotlin: Algorithm(Kotlin)

 

문제 요약

3x3 숫자 퍼즐에서 빈 칸을 움직여가며 모든 숫자를 정렬할 때, 최단 거리를 구하라. (불가능은 -1)

 

조건

• 시간 제한: 1초
• 메모리 제한: 256MB(Kotlin/JVM)

 

풀이

• 빈 칸 '0' 을 BFS 로 움직여가며 최단경로 찾기
• 중복 방지를 위해 이동시마다 퍼즐의 상태를 set으로 저장
• (핵심1) 퍼즐의 상태를 2차원 배열이 아닌 String 객체로 저장해야 set 활용이 가능하다.
• (핵심2) 퍼즐 조각을 이동시킬 때 String 객체의 1차원 index를 활용해 움직이지만, 퍼즐 조각은 2차원 배열 판에서의 이동된다는 것을 주의해야 함

 

const val DEST = "123456780"
val RANGE = 0..2
val DX = intArrayOf(-1, 0, 1, 0)
val DY = intArrayOf(0, -1, 0, 1)

fun main() {
    var puzzle = ""

    for (i in 0 until 3) {
        puzzle += readLine()
    }

    solution(puzzle.replace(" ", ""))
        .let { println(it) }
}

fun solution(puzzle: String): Int {
    if (puzzle == DEST)
        return 0

    val puzzleSet = mutableSetOf(puzzle)
    val queue = ArrayDeque(listOf(puzzle))

    var count = 0 // 이동 횟수

    while (queue.isNotEmpty()) { // BFS
        count++

        for (i in queue.indices) { // BFS 한 사이클
            val p = queue.poll()
            val idx = p.indexOf('0')

            for (dir in 0 until 4) { // 빈 칸('0') 상, 하, 좌, 우 이동
                val next = p.move(idx, dir)
                    ?: continue

                if (next == DEST) // 정렬 완료
                    return count

                if (puzzleSet.contains(next)) // 중복 체크
                    continue

                queue.offer(next)
                puzzleSet.add(next)
            }
        }
    }

    return -1
}

private fun String.move(i: Int, d: Int): String? {
    val nx = i % 3 + DX[d]
    val ny = i / 3 + DY[d]
    if (nx !in RANGE || ny !in RANGE)
        return null

    val ni = ny * 3 + nx
    val sb = StringBuilder(this)
    sb.setCharAt(i, this[ni])
    sb.setCharAt(ni, this[i])
    return sb.toString()
}