체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?
[입력 조건]
입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.
[출력 조건]
각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.
내가 해결한 방법
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
private val dxy = arrayOf(Pair(-1, -2), Pair(1, -2), Pair(-2, -1), Pair(2, -1),
Pair(2, 1), Pair(-2, 1), Pair(-1, 2), Pair(1, 2))
fun main(){
val br = BufferedReader(InputStreamReader(System.`in`))
val tc = br.readLine().toInt()
var stk : StringTokenizer
repeat(tc){
val length = br.readLine().toInt()
stk = StringTokenizer(br.readLine())
val cur = Pair(stk.nextToken().toInt(), stk.nextToken().toInt()) // 현재위치 입력
stk = StringTokenizer(br.readLine())
val next = Pair(stk.nextToken().toInt(), stk.nextToken().toInt()) // 목적지 입력
if(cur == next){ // 현재와 목적지가 같을 때
println(0)
}else {
println(knightMove(length, cur, next))
}
}
}
fun knightMove(length: Int, cur: Pair<Int, Int>, next: Pair<Int, Int>): Int{
val visited = Array(length){ BooleanArray(length) } // 방문 처리
visited[cur.first][cur.second] = true
val q : Queue<Triple<Int, Int, Int>> = LinkedList()
q.add(Triple(cur.first, cur.second, 0)) // x좌표, y좌표, cost
while(q.isNotEmpty()){
val pos = q.poll()
for(i in dxy){
val dx = pos.first + i.first
val dy = pos.second + i.second
if(dx < 0 || dy < 0 || dx >= length || dy >= length || visited[dx][dy])
continue
if(dx == next.first && dy == next.second) {
return pos.third + 1
}
q.add(Triple(dx, dy, pos.third + 1))
visited[dx][dy] = true
}
}
return 0
}
움직일 수 있는 경우의 수를 만들어 놓고, 큐에 현재 위치와 지금까지 걸린 시간을 함께 Triple로 구성하여 삽입한다. 큐에서 하나씩 빼서 움직일 수 있는 경우를 더해 목적지에 도달했는지를 확인하고, 목적지에 도달하지 않았으면 움직인 좌표와 시간 + 1을 다시 큐에 삽입한다.
