[백준/BOJ] 7562번: 나이트의 이동

문제

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

7562번: 나이트의 이동

해설

bfs의 기본적인 문제이다.

보통은 상하좌우 4방향으로만 이동하지만, 이 문제에서는 총 8방향으로 이동할 수 있다.

도착점에 도착하게 되면 bfs를 종료하고, 움직인 횟수를 출력하면 된다.

소스 코드

import java.util.*

private val dy = intArrayOf(1, 1, -1, -1, 2, 2, -2, -2)
private val dx = intArrayOf(-2, 2, -2, 2, -1, 1, -1, 1)
private var totalCnt = 0

fun main() = with(System.`in`.bufferedReader()) {
    val testCase = readLine().toInt()
    repeat(testCase) {
        val len = readLine().toInt()
        val visited = Array(len) { BooleanArray(len) }

        val (curY, curX) = readLine().split(" ").map { it.toInt() }
        val (targetY, targetX) = readLine().split(" ").map { it.toInt() }
        moveKnight(visited, curY, curX, targetY, targetX, len)

        println(totalCnt)
    }
}

private fun moveKnight(visited: Array<BooleanArray>, curY: Int, curX: Int, targetY: Int, targetX: Int, len: Int) {
    val que: Queue<Pair<Pair<Int, Int>, Int>> = LinkedList()
    que.add(Pair(Pair(curY, curX), 0))
    visited[curY][curX] = true

    while(que.isNotEmpty()) {
        val y = que.peek().first.first
        val x = que.peek().first.second
        val cnt = que.peek().second
        que.poll()

        if(y == targetY && x == targetX) {
            totalCnt = cnt
            return
        }

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

            if(ny !in 0 until len || nx !in 0 until len || visited[ny][nx]) continue
            que.add(Pair(Pair(ny, nx), cnt + 1))
            visited[ny][nx] = true
        }
    }
}