[백준] 7562 - 나이트의 이동

체스에서 나이트의 움직임은 횡으로 +- 1을 하는 경우, 종으로 +-2를 한다.
이러한 특징을 이용하여 l * l 의 격자 (2차원 배열) 과 BFS 를 활용, 답을 도출해내면 된다.

풀이

/*
* 나이트가 움직이는 방향은 x +- 2, y +- 1 이거나 x +- 1, y +- 2 이다.
*
* 첫째줄 - 테스트 케이스 개수
* 첫째 줄 - 체스판 한 변의 길이 l
* 둘째 줄 - 나이트가 현재 있는 칸
* 셋째 줄 - 나이트가 이동하려는 칸
* 체스판의 크기는 l * l, 각 칸은 0 .. l - 1
* */

private val dx = intArrayOf(-2, -2, +2, +2, -1, +1, -1, +1)
private val dy = intArrayOf(-1, +1, -1, +1, -2, -2, +2, +2)
private var l = 0
private lateinit var chessBoard: Array<IntArray>
private var stringBuilder = StringBuilder()

fun `7562-나이트의 이동`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val t = br.readLine().toInt()

    repeat(t){
        l = br.readLine().toInt()
        // 방문했는지 이것으로 확인
        chessBoard = Array(l){ IntArray(l){ -1 } }
        val (currentX, currentY) = br.readLine().split(" ").map { it.toInt() }
        val (goalX, goalY) = br.readLine().split(" ").map { it.toInt() }

        bfs(currentX, currentY, goalX, goalY)
    }

    bw.write(stringBuilder.toString())
    bw.flush()
    bw.close()
    br.close()
}

private fun bfs(startX: Int, startY: Int, goalX: Int, goalY: Int){
    val arrayDeque = ArrayDeque<Pair<Int, Int>>()

    arrayDeque.add(startX to startY)
    /*
    * 첫 시작은 0번 움직였으므로 0을 넣어준다.
    * */
    chessBoard[startX][startY] = 0

    while(arrayDeque.isNotEmpty()){
        val currentLocation = arrayDeque.removeFirst()
        val x = currentLocation.first
        val y = currentLocation.second

        if(x == goalX && y == goalY){
            if(stringBuilder.isNotEmpty()) stringBuilder.append("\n")
            stringBuilder.append("${chessBoard[x][y]}")
            break
        }

        for(i in 0 until 8){
            val nx = x + dx[i]
            val ny = y + dy[i]

            /*
            * 이동한 칸이 아닌 경우에만 진행
            * */
            if(nx in 0 until l && ny in 0 until l && chessBoard[nx][ny] == -1){
                chessBoard[nx][ny] = chessBoard[x][y] + 1
                arrayDeque.addLast(nx to ny)
            }
        }
    }
}

후기

처음에는 chessBoard 를 IntArray 가 아닌 BooleanArray 로 주고, Count 를 while 에 넣어 증가시키는 코드로 짜 틀린 답안을 제출하였다.

그래서 코드를 다시 살펴본 결과 while 에 Count 를 넣게 되면 독립된 count 가 아닌, 하나의 count 를 모든 움직임에서 쓰게 된다는 문제를 파악했고, chessBoard 배열을 Array 로 변경하였다.

그러나 초기화 값은 0이 아닌 -1로 주었는데, 나이트가 놓여지는 첫 칸의 경우 0칸 움직였다는 것을 표시해야했기 때문이다.

만약 모든 초기값을 0으로 주었다면, if에서 나이트가 놓여진 첫 칸에 방문기록이 주어지지 않아 이상한 값이 출력되었을 것이다.