백준 1525번: 퍼즐 (Kotlin)

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

1525번: 퍼즐

안녕하세요, 이륙사입니다.

 

풀이

이번 문제는 BFS 기반의 완전탐색 문제였습니다.

 

초기 상태에서 한번의 이동으로 만들 수 있는 모든 상태(노드)를 탐색합니다. 원하는 상태를 찾지 못했다면, 바뀐 상태에서 다음 이동으로 만들 수 있는 모든 상태들을 확인합니다. 이걸 반복하다 보면 원하는 상태를 찾게 되는데, 그 때까지 움직인 횟수가 정답이 됩니다. 왜냐면 한 번 움직일 때마다 만들 수 있는 상태를 모두 차례대로 확인했기 때문입니다. 따라서, BFS로 문제를 해결할 수 있습니다.

 

방문 검사

퍼즐 문제에서 가장 어려운 부분이 아마 이차원 상태에 대한 중복 방문 처리일 것입니다. 같은 숫자를 다시 확인하면 정답을 찾을 수 없는 입력이 주어지면 무한 루프에 빠질 수 있기 때문입니다. 여기서 핵심은 상태(노드)가 이차원 배열로 표현되어 있다는 겁니다.

 

그래프 탐색 문제를 풀다보면 이차원 배열 자체를 그래프라고 착각할 수도 있는데요, 이 문제에선 이차원 배열 자체가 하나의 노드가 됩니다. 

 

 

이차원 배열은 사실 노드를 표현하기 위한 수단일 뿐이었고, 그림처럼 문자열이나 숫자로도 나타낼 수 있는 것입니다!

그러면 Map 자료구조를 사용해서 해당 상태를 확인했는지에 대한 처리가 가능해집니다.

숫자(상태)와 0의 위치로 구성된 노드

Queue 안에서 문자를 교환할 때는 인덱스로 접근하기 위해 String을 사용하고, visited에서는 Int형을 사용하면 시간,공간 복잡도를 좀 더 효율적으로 구성할 수 있습니다. 

 

시간 복잡도)

9개의 자리에 각 수를 하나씩 넣을 수 있으므로 탐색하게 되는 최대 상태(노드) 수는 9! = 362,880개이고, 각 상태는 4개의 새로운 상태(엣지)를 고려하므로 O(V + E) = 9! + 9! * 4 = 약 180만입니다. 따라서, 시간제한 내에 해결할 수 있습니다.

 

생각 과정

1. 초기 상태에서 가까운 순서대로 가능한 모든 경우를 탐색하는 BFS 문제임을 확인한다.
2. 중복 확인 처리를 하지 않으면 무한 루프에 빠지거나 시간 복잡도가 엄청 커진다.
3. 2차원 배열 -> 1차원 배열 -> 문자열의 사고 과정을 통해 각 상태를 다르게 표현할 수 있다는 걸 떠올릴 수 있다.  

 

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.pow

const val TARGET = "123456780"

data class Node(val number: String, val zeroRow: Int, val zeroCol: Int)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var row = 0
    var col = 0
    val sb = StringBuilder()

    for (i in 0 until 3) {
        val st = StringTokenizer(readLine())

        for (j in 0 until 3) {
            val number = st.nextToken()

            if (number == "0") {
                row = i
                col = j
            } 
            
            sb.append(number)
        }
    }
    
    print(getMinCount(sb.toString(), row, col)) // bfs 탐색
}

fun getMinCount(startState: String, zeroRow: Int, zeroCol: Int): Int {
    val q: Queue<Node> = LinkedList()
    val visited = HashMap<Int, Int>() // 방문 검사 겸 이동 횟수 저장
    val dRow = arrayOf(-1, 1, 0, 0)
    val dCol = arrayOf(0, 0, -1, 1)
    
    q.add(Node(startState, zeroRow, zeroCol))
    visited[startState.toInt()] = 0

    while (q.isNotEmpty()) {
        val node = q.poll()
        val currentVisitOrder = visited[node.number.toInt()]!!
        
        // 목표 상태일 때
        if (node.number == TARGET) {
            return currentVisitOrder
        }

        for (i in 0 until 4) {
            val nextRow = node.zeroRow + dRow[i]
            val nextCol = node.zeroCol + dCol[i]
            
            // 퍼즐(번호) 범위 바깥이면
            if (nextRow !in 0 until 3 || nextCol !in 0 until 3) {
                continue
            }

            // 9(빈칸)와 인접한 번호 위치 변경
            val nextNumber = StringBuilder(node.number).apply {
                val zeroIndex = 3 * node.zeroRow + node.zeroCol
                val nextIndex = 3 * nextRow + nextCol
                this.replace(zeroIndex, zeroIndex + 1, this[nextIndex].toString())
                this.replace(nextIndex, nextIndex + 1, "0")
            }.toString()
            val intNumber = nextNumber.toInt()

            // 방문 검사
            if (visited.containsKey(intNumber)) {
                continue
            }

            q.add(Node(nextNumber, nextRow, nextCol))
            visited[intNumber] = currentVisitOrder + 1
        }
    }

    return -1
}