[BaekJoon] 7562번 나이트의 이동(Kotlin) 문제 풀이 [Silver 1]

문제

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

7562번: 나이트의 이동

 

어떻게 풀 것인가?

문제에서 주어진 그림과 같이 8방향에 대하여 BFS 탐색을 진행하면서

목적지에 도달하면 즉시 bfs에서 result값을 저장하고 리턴한다.

 

풀면서 놓쳤던점

X

 

이 문제를 통해 얻어갈 것

BFS의 다양한 방향 탐색

 

내 코드 

import java.lang.StringBuilder
import java.util.*

// 백준알고리즘 7562번 나이트의 이동
private var dx: IntArray = intArrayOf(1, 2, 2, 1, -1, -2, -1, -2)
private var dy: IntArray = intArrayOf(2, 1, -1, -2, -2, -1, 2, 1)
private lateinit var start: Pair
private lateinit var end: Pair
private var result = 0
private var num: Int = 0
private lateinit var visit: Array<Array<Boolean>>

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

fun main() = with(System.`in`.bufferedReader()) {
    val test_case = readLine().toInt()
    val sb = StringBuilder()
    repeat(test_case) {
        num = readLine().toInt()
        result = 0
        visit = Array(num) { Array(num) { false } }
        val (x1, y1) = readLine().split(" ").map { it.toInt() }
        start = Pair(x1, y1)
        val (x2, y2) = readLine().split(" ").map { it.toInt() }
        end = Pair(x2, y2)
        bfs()
        sb.append(result).append("\n")
    }
    print(sb)
}

private fun bfs() {
    if (start == end) {
        return
    }
    val que: Queue<Pair> = LinkedList()
    que.offer(start)
    visit[start.x][start.y] = true
    result = 1
    while (que.isNotEmpty()) {
        val size = que.size
        for (i in 0 until size) {
            val cur = que.poll()
            for (i in 0 until 8) {
                val curX = cur.x + dx[i]
                val curY = cur.y + dy[i]
                if (range(curX, curY) || visit[curX][curY]) continue
                if (curX == end.x && curY == end.y) return
                visit[curX][curY] = true
                que.offer(Pair(curX, curY))
            }
        }
        result++
    }
}

private fun range(x: Int, y: Int): Boolean {
    return (x !in 0 until num) || (y !in 0 until num)
}

 

참고

X