BOJ-7562 나이트의 이동 Swift

문제

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

입력

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

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

출력

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

내가 푼 풀이

- 주어진 체스판에서 시작점부터 BFS 탐색으로 이동한 곳에 +1 카운트를 해준다.

- 따로 카운트해줄 배열 dp를 선언해 저장하고, 도착점이 목적지랑 같은경우 탐색 종료해준다.

 

import Foundation

let c = Int(readLine()!)!

// 나이트의 이동
var dx = [1, 2, -1, -2, 1, 2, -1, -2]
var dy = [2, 1, -2, -1, -2, -1, 2, 1]

for i in 0..<c {
    var len = Int(readLine()!)!
    var board = Array(repeating: Array(repeating: 0, count: len), count: len)
    var dp = Array(repeating: Array(repeating: 0, count: len), count: len)
    var s = readLine()!.split(separator: " ").map{ Int($0)! }
    var d = readLine()!.split(separator: " ").map{ Int($0)! }
    
    var needVisitQueue = [(x: s[0], y: s[1])]
    
    // BFS
    // 나이트를 움직일때 도착점이 탐색하지 않은곳이라면 +1 카운트
    // 이미 도착했던곳이라면 스킵한다.
    while !needVisitQueue.isEmpty {
        var loc = needVisitQueue.removeFirst()
        if loc.x == d[0] && loc.y == d[1] { break }
        
        for i in 0..<8 {
            var mx = loc.x + dx[i]
            var my = loc.y + dy[i]
            
            if (mx >= 0 && mx < len) && (my >= 0 && my < len) && (dp[mx][my] == 0){
                dp[mx][my] = dp[loc.x][loc.y] + 1
                needVisitQueue.append((x: mx, y: my))
            }
        }
    }
    print(dp[d[0]][d[1]])
}