나이트이동

---

title: “7562 - 나이트의 이동”
date: “2019-02-16”

category: “algorithm”

문제요약

1. 테스트 케이스의 수가 입력으로 주어진다.
2. 각 테스트 케이스 마다 입력으로는 체스판의 크기와, 현재 나이트의 위치, 이동하려는 위치가 주어진다.
3. 각 테스트 케이스에서 나이트는 몇번 이동해야 목적지로 이동할 수 있는지 출력하시오.

접근법

기존에 풀어본 문제중에서는 미로탐색(2178)과 가장 유사한것 같다. 미로탐색 문제의 경우 인접한(상하좌우) 칸으로 1칸씩만 이동할 수 있었고, 벽이 존재하여, 벽이 있는 경우 이동할 수 없다는 문제였다. 그러나 이 문제에서는 벽이 존재하지 않기 때문에 어디로든 이동할 수 있고, 인접한 칸으로 이동하는 것이 아니라 체스의 나이트와 같이 움직일 수 있다.
벽이 존재하지 않는다는 특징 때문에 미로탐색보다 더 쉬운 문제라고 생각한다. 현재 좌표에서 다음좌표로 갈때, 미로탐색 문제에서는 현재 좌표에서 y값에 1을 더해주거나, 빼주거나 x값에 1을 더해주거나, 빼주는 방법을 사용했다면 이번 문제에서는 나이트처럼 이동할 수 있도록 현재 좌표의 y, x에 적절한 값을 더해주거나 빼주면 문제를 풀 수 있다.

어렵지 않은 문제이므로 간단히 설명해보면, 현재 좌표를 기준으로 나이트가 움직이는 형태로 이동했을 때 좌표를 계산한다. 이렇게 계산된 좌표중 아직 방문한 적이 없는 좌표를 Queue에 넣으며 목적지를 방문할 때까지 탐색을 진행한다. 만약 목적지에 도착했다면 탐색을 중지하고 몇번의 이동만에 목적지에 도착했는지 출력한다. 이를 위해 지금까지 방문한 좌표를 기록하는 배열이 필요하고, 해당 배열의 좌표에 몇번째 이동만에 해당 좌표로 갔는지 기록해 놓으면 쉽게 문제를 풀 수 있을 것이다.

Source Code

소스코드 보러가기

• 아직 주석이 달려있지 않습니다.
• pseudocode 보다는 python 코드를 올릴 예정입니다.
• Code Review는 언제나 환영합니다 (코드를 더 깔끔하게, 효율적으로 만드는걸 도와주세요!)