[백준 7562번] [Kotlin] 나이트의 이동

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

7562번: 나이트의 이동

 

난이도 : 실버 1
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색

 

 

설명

특정 위치로 이동할 수 있는 가장 적은 횟수를 찾는 문제입니다.

bfs를 활용할 수 있겠는데요.

단순히 4방향 bfs가 아닌 나이트의 이동에 맞춘 8방향 bfs를 사용하면 될 것 같습니다.

 

 

나이트의 이동은 상,하,좌,우 중 2칸 이동하고, 수직방향으로 1칸

혹은 상하좌우 1칸 이동 후 이동방향의 대각선 방향 1칸 이동으로 볼 수 있습니다.

 

그럼, 8방향을 좌표로 나타내면 어떨까요?

 

 

 

기준점에 대해 위와 같이 나타낼 수 있습니다.

 

dfs/bfs에서 상하좌우 이동을

dx = {1,-1,0,0}

dy = {0,0,1,-1}과 같이 나타내듯이,

나이트의 이동을 아래와 같이 나타낼 수 있습니다.

 

 

 

 

이후 내용은 일반적인 bfs와 동일합니다.

 

 

 

 

소스코드

 

import java.util.*

data class Point(val x: Int, val y: Int)

fun main() = with(System.`in`.bufferedReader()) {
    val sb = StringBuilder()

    // 나이트가 이동할 수 있는 방향
    val dx = intArrayOf(-2, -1, 1, 2, 2, 1, -1, -2)
    val dy = intArrayOf(1, 2, 2, 1, -1, -2, -2, -1)

    repeat(readLine().toInt()) {
        val n = readLine().toInt()

        val startXY = readLine().split(" ").map { it.toInt() }
        val start = Point(startXY[0], startXY[1])
        val endXY = readLine().split(" ").map { it.toInt() }
        val end = Point(endXY[0], endXY[1])

        // data class를 == 로 비교하면 내부의 값이 같은지 비교 (equals와 같은 역할)
        if (start == end) {
            sb.append(0).append("\n")
            return@repeat
        }


        // 일반적인 bfs와 동일
        val visited = Array(n) { IntArray(n) }

        val q = LinkedList<Point>() as Queue<Point>
        q.offer(start)
        visited[start.x][start.y] = 1

        bfs@ while (q.isNotEmpty()) {
            val target = q.poll()

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

                if (nx !in 0 until n || ny !in 0 until n || visited[nx][ny] != 0) continue

                if (nx == end.x && ny == end.y) {
                    sb.append(visited[target.x][target.y]).append("\n")
                    break@bfs
                }

                visited[nx][ny] = visited[target.x][target.y] + 1
                q.offer(Point(nx, ny))
            }
        }
    }

    print(sb)
}

 

 

 

 

후기

일반적인 4방향 bfs와 달리,

조금 특이한 bfs 탐색 방법이였습니다.