[백준][코틀린][16948] 데스 나이트

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

16948번: 데스 나이트

문제 풀이

1. N X N 크기의 2차원 BooleanArray visit  를 선언하여 이미 탐색했는 지 유무를 저장한다.

2. Position data class 를 선언하고 r, c 좌표를 파라미터로 받는다.

3. DeathNight data class 를 선언하고 Position, Count(이동 횟수) 를 파라미터로 받는다.

4. BFS 로 탐색하여 Queue 에서 pop 으로 추출한 좌표가 도착지점의 좌표와 같을 경우 Count 를 Return 한다.

5. 도착 지점을 만나지 못할 경우 -1 을 Return 한다.

코드

import java.io.*
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    val (r1, c1, r2, c2) = br.readLine().split(" ").map { it.toInt() }
    println("${bfs(N, Position(r1, c1), Position(r2, c2))}")
}

private fun bfs(N: Int, start: Position, end: Position): Int {
    val queue = LinkedList<DeathNight>()
    queue.add(DeathNight(start, 0))
    val visit = Array(N) { BooleanArray(N) { false } }
    visit[start.r][start.c] = true

    while (queue.isNotEmpty()) {
        val (cPos, cCount) = queue.pop()
        //println("current $cPos, $cCount")

        if (cPos.r == end.r && cPos.c == end.c) {
            return cCount
        }

        //  (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1) 로 이동 가능.
        val dR = intArrayOf(-2, -2,  0, 0,  2,  2)
        val dC = intArrayOf(-1,  1, -2, 2, -1,  1)

        for (i in 0..5) {
            val nR = cPos.r + dR[i]
            val nC = cPos.c + dC[i]

            // 범위 밖
            if ((nR < 0 || nR >= N) || (nC < 0 || nC >= N)) continue
            // 이미 탐색한 영역
            if (visit[nR][nC]) continue

            //println("next ($nR, $nC), $cCount")
            visit[nR][nC] = true
            queue.add(DeathNight(Position(nR, nC), cCount + 1))
        }
    }

    return -1
}

private data class Position(val r: Int, val c: Int)

private data class DeathNight(val pos: Position, val count: Int)