7562 나이트 무브먼트
문제 요약
체스판에서 기사를 움직일 때 특정 (y, x)에 도달하는 데 걸리는 이동 횟수를 계산해야 합니다. 즉, 도달할 최단거리(y,x)를 찾는 것이 문제임을 알 수 있다.
연산
- 테스트 사례를 최대한 반복합니다.
- 체스판의 크기, 시작 위치 및 목표 위치가 입력됩니다.
- 체스판의 크기와 동일한 방문 배열을 선언합니다.
- BFS를 수행하여 최단 거리를 계산합니다.
접근하다
- 점퍼의 이동 방향을 잘 계산해야 합니다. (좌표를 그려서 생각하자)
- 가장 짧은 거리이므로 방문한 배열을 int로 선언하고 각 이동에 +1을 더하여 깊이를 얻습니다.
- 목표 지점에 도달하면visited(goalY)(goal(X) – 1을 인쇄해야 합니다. 이것이 혼동스럽다면 Visited를 -1!로 초기화하거나 Visited(y)(x)!로 직접 인쇄할 수 있습니다.
- 이동 없이 첫 번째 위치에 도달했으므로 깊이는 0이지만 방문은 단순성을 위해 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
}