[백준] 퍼즐 (Kotlin)

문제 바로가기

0과 인접한 수를 바꾸는 행위를 하는 여러가지 경우의 수를 간보면서 최소 이동횟수를 구하는 문제이기 때문에 BFS로 접근하여 생각해볼 수 있습니다.

이렇게 'BFS'로 접근해야함은 알아챘지만, 처음에는 2차원 배열을 1차원으로 치환하여 푸는 방법은 생각하지 못하였습니다. 그래서 필자는 그냥 2차원 배열에서 배열을 깊은복사로 업데이트하면서 해결하려고 노력하다가
visit 배열(역할을 하는?)을 과연 어떤 자료구조로 관리해야할까? 라는 고민에서 많이 막혔던 것 같았습니다. 그래서 결국 레퍼런스를 찾아보니, 0과 인접한 수가 스왑될 때마다 업데이트된 배열의 상태, 그 시점의 스냅샷 상태를 저장할 배열로 가장 효율적인 방법은 2차원 배열을 1차원 문자열로 치환하여 상태를 저장하는 방식이었습니다. Set 자료구조를 visit 배열 역할로 하는 자료구조로 선정하여, 한 번 스냅샷에 찍힌 상태 (처음 상태 포함)는 중복되지 않게 저장하며, bfs로 접근하여 문제를 해결하였습니다.

풀이 코드 (kotlin)

import java.util.LinkedList
import java.util.Queue

private val dx = intArrayOf(-1, 1, 0, 0)
private val dy = intArrayOf(0, 0, -1, 1)
private val visited = mutableSetOf<String>()
private const val standard = "123456780"

fun main() {
    var initial = ""

    repeat(3) {
        initial += readln().replace(" ", "")
    }

    println(bfs(initial))
}

private fun bfs(str: String): Int {
    val q: Queue<Pair<String, Int>> = LinkedList()
    q.add(Pair(str, 0))
    visited.add(str)

    while (q.isNotEmpty()) {
        val cur = q.poll()
        val coord = cur.first.indexOf('0')
        val x = coord / 3
        val y = coord % 3
        if (cur.first == standard) return cur.second
        for (i in 0 until 4) {
            val nx = x + dx[i]
            val ny = y + dy[i]
            if (nx !in 0 until 3 || ny !in 0 until 3) continue
            val nc = nx * 3 + ny
            val tmp = cur.first.toCharArray()
            tmp[coord] = tmp[nc].also { tmp[nc] = tmp[coord] }
            val newString = String(tmp)
            if (!visited.contains(newString)) {
                q.add(Pair(newString, cur.second + 1))
                visited.add(newString)
            }
        }
    }
    return -1
}