[Swift] 7562 - 나이트의 이동

7562 나이트의 이동

문제로 이동

문제 요약

체스 판 위에 나이트를 이동시키면서 특정 (y, x)에 도달하기 위해 몇 번 움직여야하는지 계산해야한다. 즉, (y, x)에 도달하기 위한 최단거리가 얼마인지 구하는 문제라는 것을 알 수 있다.

알고리즘

1. test case만큼 반복한다.
2. 체스 판의 크기, 시작 위치, 목표 위치를 입력받는다.
3. 체스 판의 크기만큼 visited 배열을 선언한다.
4. BFS를 수행해서 최단거리를 계산한다.

접근방법

• 나이트의 이동방향을 잘 계산해야한다. (좌표를 그려서 생각해보자)
• 최단거리이기 때문에 visited 배열을 Int로 선언하고, 움직일 때마다 +1을 해서 depth를 구하자.
• 목표 지점에 닿았다면, visited[goalY][goal[X] - 1을 출력해야한다.이것이 헷갈린다면 visited를 -1로 초기화해도 된다! 또는 visited[y][x]로 바로 출력해버리자!
• 첫 위치는 움직이지 않고 도달하기 때문에 depth는 0인데, 편의상 visited에 1로 방문처리 했기 때문이다.
• 만약 시작 위치가 목표지점이라면 0을 출력해야한다.

코드

let dy = [2, 2, 1, 1, -1, -1, -2, -2]
let dx = [-1, 1, -2, 2, -2, 2, -1, 1]
var visited = [[Int]]()

let testCase = Int(readLine()!)!

for _ in 0 ..< testCase {
    let l = Int(readLine()!)!
    let input = readLine()!.split { $0 == " " }.map { Int($0)! }, (x, y) = (input[0], input[1])
    let input2 = readLine()!.split { $0 == " " }.map { Int($0)! }, (goalX, goalY) = (input2[0], input2[1])
    visited = [[Int]](repeating: [Int](repeating: 0, count: l), count: l)
    print(bfs(y, x, goalY, goalX, l))
}

func bfs(_ y: Int, _ x: Int, _ goalY: Int, _ goalX: Int, _ l: Int) -> Int {
    guard (y, x) != (goalY, goalX) else { return 0 }
    var queue = [(y, x)]
    visited[y][x] = 1
    
    while !queue.isEmpty {
        let (y, x) = queue.removeFirst()
        for i in 0 ..< dy.count {
            let ny = dy[i] + y
            let nx = dx[i] + x
            
            guard 0..<l ~= ny && 0..<l ~= nx && visited[ny][nx] == 0 else { continue }
            visited[ny][nx] = visited[y][x] + 1
            if ny == goalY && nx == goalX { return visited[y][x] }
            queue.append((ny, nx))
        }
    }
    return 0
}