[swift] 백준 - 7562번: 나이트의 이동

문제 링크

7562번: 나이트의 이동

---

문제

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

입력

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

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

출력

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

예제

---

성공 풀이

import Foundation

let dy = [1,2,2,1,-1,-2,-2,-1]
let dx = [-2,-1,1,2,2,1,-1,-2]

for _ in 0..<Int(readLine()!)! {
    let length = Int(readLine()!)!
    let S = readLine()!.split { $0 == " " }.map { Int($0)! }
    let G = readLine()!.split { $0 == " " }.map { Int($0)! }
    var queue = [(S,0)]
    var visited = Array(repeating: Array(repeating: false, count: length), count: length)
    visited[S[0]][S[1]] = true
    
    while !queue.isEmpty {
        let current = queue.removeFirst()
        if current.0 == G {
            print(current.1)
            break
        }
        for i in 0..<dy.count {
            let my = current.0[0] + dy[i]
            let mx = current.0[1] + dx[i]
            
            guard my >= 0 && my < length && mx >= 0 && mx < length && !visited[my][mx] else { continue }
            visited[my][mx] = true
            queue.append(([my,mx],current.1+1))
        }
    }
}

풀이 키워드

• 나이트가 갈 수 있는 8가지 방향을 고려하여 queue역할을 해주는 배열에 담아 너비우선탐색으로 목적지에 도착하는 최소 count를 구했습니다.