[백준][코틀린] 7562 나이트의 이동

문제 내용

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, …, l-1} × {0, …, l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

예제 입력	예제 출력
3 8 0 0 7 0 100 0 0 30 50 10 1 1 1 1	5 28 0

문제 풀이

전형적인 BFS 코드에서 달라진 점은 나이트가 움직이는 것이 단순 상하좌우가 아니라는 점이다. 

step을 나이트의 이동범위에 따라 변경해주는 것 외에는 크게 변경 된 것이 없다!

</>̆̈ 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

private val br = BufferedReader(InputStreamReader(System.`in`))
private val stepX = listOf(1, 1, 2, 2, -1, -1, -2, -2)
private val stepY = listOf(2, -2, 1, -1, 2, -2, 1, -1)

private var mapSize = 0
private lateinit var visited: Array<BooleanArray>
private lateinit var goal: List<Int>

fun main() {
    for (test in 0 until br.readLine()!!.toInt()) {

        mapSize = br.readLine().toInt()
        visited = Array(mapSize) {BooleanArray(mapSize)}
        val curPoint = br.readLine().split(" ").map { it.toInt() }
        goal = br.readLine().split(" ").map { it.toInt() }

        println(bfs(curPoint[0], curPoint[1]))
    }
}

private fun bfs(x: Int, y: Int) : Int{
    val queue = LinkedList<Triple<Int, Int, Int>>()
    queue.add(Triple(x, y, 0)); visited[x][y] = true

    while (queue.isNotEmpty()) {
        val (cx, cy, route) = queue.poll()

        if (cx == goal[0] && cy == goal[1]) return route

        for (step in 0 until 8) {
            val nx = cx + stepX[step]; val ny = cy + stepY[step]

            if (nx in 0 until mapSize && ny in 0 until mapSize && !visited[nx][ny]) {
                queue.offer(Triple(nx, ny, route+1))
                visited[nx][ny] = true
            }
        }

    }

    return -1
}

링크

7562번: 나이트의 이동