[백준 1525번] [Kotlin] 퍼즐

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

1525번: 퍼즐

 

난이도 : 골드 2
태그 : 자료 구조, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 해시를 사용한 집합과 맵

 

 

설명

BFS + Map을 사용한 문제입니다.

처음에는 9개 좌표의 방문체크를 어떻게 해야하나... 9차원 visited 배열...?을 생각했으나,

그냥 Map<String, Int>을 사용해 방문체크를 할 수 있습니다.

 

103

425

786 

위의 3x3 퍼즐이 주어졌다면, 이를 103425786와 같이 문자열 혹은 CharArray 형태로 바꿔 생각할 수 있습니다.

즉, map["103425786"] = 0 이며,

3과 0의 위치를 바꾼다면 130425786, map["130425786"] = 1이 됩니다.

이와 같이, map과 String을 사용해 방문체크를 하는게 핵심인 문제입니다.

이미 방문체크가 되어있을 때, 더 작은 값으로 갱신할 필요는 없습니다. BFS 특성 상 첫 값이 무조건 최단경로기 때문에,

첫 값 이후에 들어오는 값은 모두 최단 경로가 아니기 때문입니다.

 

최우측하단에는 빈 칸(0)이 와야 하는데, 0보다는 9가 익숙하니, 0을 9로 대신 입력 받았습니다.

 

 

 

소스코드

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

fun main() = with(System.`in`.bufferedReader()) {

    val dx = arrayOf(0, 0, 1, -1)
    val dy = arrayOf(1, -1, 0, 0)

    val nums = Array(9) { ' ' }
    repeat(3) { i ->
        val st = StringTokenizer(readLine())
        repeat(3) { j ->
            val n = st.nextToken()[0]
            nums[i * 3 + j] = if (n == '0') '9' else n
        }
    }

    val q = LinkedList<String>() as Queue<String>
    val map = HashMap<String, Int>()

    q.offer(nums.joinToString(""))
    map[nums.joinToString("")] = 0

    while (q.isNotEmpty()) {
        val target = q.poll()
        val nineIdx = target.indexOf("9")

        // 인덱스 -> 좌표화
        val x = nineIdx / 3
        val y = nineIdx % 3

        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 newIdx = nx * 3 + ny // 좌표 -> 인덱스화
			
            
            // 두 값을 서로 바꿈
            val charArray = target.toCharArray()
            charArray[nineIdx] = charArray[newIdx]
            charArray[newIdx] = '9'

            val newString = charArray.joinToString("")

            if (newString !in map) {
                map[newString] = map[target]!! + 1
                q.offer(newString)
            }
        }
    }

    println(map.getOrDefault("123456789", -1))
}

 

 

인덱스 -> 좌표화, 좌표 -> 인덱스화가 조금 낮설게 느껴지실 수 있는데, 예시를 하나 들어보겠습니다.

103

425

786 를

1차원 배열로 나타내면 103425786 이며, 인덱스는 5입니다.

5의 좌표는 1, 2 인데, 1 * 3(width) + 2 = 5로, x좌표 * 가로 + y좌표를 하면 인덱스를 도출할 수 있습니다.

반대로, 5 / 3 = 1, 5 % 3 = 2로,

(index) / (width)를 하면 x좌표를, (index) % (width)를 하면 y 좌표를 도출할 수 있습니다.

 

 

 

후기

맵 자료구조를 사용한 BFS라는 점이 꽤 신선했습니다.