[Joco][백준/BOJ] 16959 번: 체스판 여행 1 - Kotlin

[문제]

16959번: 체스판 여행 1

[깃허브]

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

 

 

문제 요약

• 모든 칸에 순서가 매겨진 N × N 체스판에서 1번부터 시작해서 N^2까지 순서대로 방문할 때 걸리는 최단 시간 구하기
• 3가지의 체스 말 나이트, 룩, 비숍을 사용하며, 각 턴마다 이동 혹은 말 변경을 할 수 있음

 

제한 조건

• 시간 제한: 2초
• 메모리 제한: 512 MB
• 체스판의 크기 N (3 ≤ N ≤ 10)

 

문제 풀이

• 1 ~ N^2 번 까지 순차적으로 BFS를 통해 방문하여 최단 시간 구하기
• (핵심 1) 말을 변경할 때에도 턴(시간)이 소모됨
• (핵심 2) n번 칸에 비숍으로는 k초에, 나이트로는 k + α초에 도착했다고 하더라도 다음 목적지인 n+1번 칸에는 나이트가 더 빠르게 가는 경우도 존재함. 즉, 각각의 목적지마다 어떤 체스말로 도착했는지를 모두 기록해야 한다.
• (핵심 3) 목적지에 따라서도 중복 체크를 다르게 한다
• 중복 체크: visited[n][piece][row][col]
  • n: 시작 지점 번호(ex. 다음 목적지가 2번이면 n=1, 목적지 번호가 하나씩 증가할 때마다 한 층씩 올라간다고 생각하면 쉽다)
  • piece: 해당 지점에 도착한 체스 말의 종류(나이트, 룩, 비숍)
  • row: 행
  • col: 열

 

 

[Solution.kt]

java.util.ArrayDeque

data class Node(
    val n: Int,
    val piece: Int,
    val row: Int,
    val col: Int,
    val time: Int
) {
    val nextNum: Int
        get() = n + 1

    fun getNext(n: Int = this.n, piece: Int = this.piece, row: Int = this.row, col: Int = this.col): Node {
        return Node(n, piece, row, col, time + 1)
    }
}

private const val NIGHT = 0
private const val BISHOP = 1
private const val ROOK = 2

private val PIECES = NIGHT..ROOK

private val MOVE = arrayOf(
    arrayOf( // NIGHT
        intArrayOf(1,-2), intArrayOf(-1,-2), intArrayOf(-2,-1), intArrayOf(-2,1),
        intArrayOf(-1,2), intArrayOf(1,2), intArrayOf(2,1), intArrayOf(2,-1)
    ),
    arrayOf( // BISHOP
        intArrayOf(-1,-1), intArrayOf(-1,1), intArrayOf(1,1), intArrayOf(1,-1)
    ),
    arrayOf( // ROOK
        intArrayOf(0,-1), intArrayOf(-1,0), intArrayOf(0,1), intArrayOf(1,0)
    ),
)

private var N = 0
private var destination = 1
private lateinit var range: IntRange
private lateinit var board: Array<IntArray>
private lateinit var visited: Array<Array<Array<BooleanArray>>>
private lateinit var queue: ArrayDeque<Node>

fun main() {
    N = readLine()!!.toInt() // 체스판의 크기 (3 ≤ N ≤ 10)

    destination = N * N
    range = 0 until N
    board = Array(N) { intArrayOf() }

    var r0 = -1 // 시작 위치 row
    var c0 = -1 // 시작 위치 col

    for (r in 0 until N) {
        board[r] = readLine()!!.split(" ")
            .map { it.toInt() } // 인덱스와 매핑하기 위해 모든 원소 -1
            .onEachIndexed { c, n -> if (n == 1) { r0 = r; c0 = c } }
            .toIntArray()
    }

    solution(r0, c0).let { println(it) }
    queue.clear()
}

fun solution(r0: Int, c0: Int): Int {
    // visited[n][p][r][c]
    // n: 체스 말의 출발 번호(0 ≤ n ≤ N^2 - 1)
    // p: piece(체스 말의 종류)
    // r: row
    // c: col
    visited = Array(destination + 1) { Array(3) { Array(N) { BooleanArray(N) } } }
    queue = ArrayDeque<Node>()

    for (p in PIECES) {
        visited[1][p][r0][c0] = true
        queue.offer(Node(1, p, r0, c0, 0))
    }

    while (queue.isNotEmpty()) {
        val cur = queue.poll()

        if (cur.n == destination) {
            queue.clear()
            return cur.time
        }

        // 1. 피스 변경
        for (p in PIECES) {
            if (p == cur.piece || visited[cur.n][p][cur.row][cur.col])
                continue

            visited[cur.n][cur.piece][cur.row][cur.col] = true
            queue.offer(cur.getNext(piece = p))
        }

        // 2. 피스 이동
        when (cur.piece) {
            NIGHT -> moveNight(cur)
            BISHOP, ROOK -> moveBishopOrRook(cur)
        }
    }

    return 0
}

private fun moveNight(cur: Node) {
    for (move in MOVE[cur.piece]) {
        val r = cur.row + move[0]
        val c = cur.col + move[1]

        if (r !in range || c !in range || visited[cur.n][cur.piece][r][c])
            continue

        visited[cur.n][cur.piece][r][c] = true

        if (board[r][c] == cur.nextNum) { // 다음 목적지 도착
            visited[cur.nextNum][cur.piece][r][c] = true

            queue.offer(cur.getNext(cur.nextNum, cur.piece, r, c))
        } else { // 미도착
            queue.offer(cur.getNext(row = r, col = c))
        }
    }
}

private fun moveBishopOrRook(cur: Node) {
    for (move in MOVE[cur.piece]) {
        var r = cur.row + move[0]
        var c = cur.col + move[1]

        while (r in range && c in range) {
            if (!visited[cur.n][cur.piece][r][c]) {
                visited[cur.n][cur.piece][r][c] = true

                if (board[r][c] == cur.nextNum) { // 다음 목적지 도착
                    visited[cur.nextNum][cur.piece][r][c] = true
                    queue.offer(cur.getNext(cur.nextNum, cur.piece, r, c))
                    break
                } else { // 미도착
                    queue.offer(cur.getNext(row = r, col = c))
                }
            }

            r += move[0]
            c += move[1]
        }
    }
}