문제 소개
좌표가 -∞에서 +∞까지 뻗어 있는 무한 체스판을 상상해 봅시다. 나이트는 [0, 0] 위치에서 출발하며, 아래 그림과 같이 총 8가지 방향으로 이동할 수 있습니다. 각 이동은 한 축 방향으로 두 칸, 그에 수직인 방향으로 한 칸 움직이는 형태입니다.
우리의 목표는 나이트를 목표 좌표 [x, y]로 옮기는 데 필요한 최소 이동 횟수를 구하는 것입니다. 문제 조건상 답은 항상 존재한다고 보장됩니다.
예시
입력이 x = 5, y = 5라면 출력은 4가 됩니다. 실제 이동 경로는 다음과 같습니다.
[0,0] → [2,1] → [4,2] → [3,4] → [5,5]
해결 접근 방법
이 문제는 재귀와 메모이제이션(메모화)을 결합하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 체스판의 대칭성 때문에 음수 좌표를 모두 절댓값으로 바꿔 제1사분면 문제로 환원할 수 있다는 점입니다. 단계별 풀이 과정은 다음과 같습니다.
(x, y) 좌표 쌍을 키로, 해당 지점까지의 최소 이동 횟수를 값으로 저장할 맵(map)을 정의합니다.
solve() 함수를 정의하고, x와 y를 인자로 전달받습니다.
기저 조건을 설정합니다. x + y = 0이면 이미 도착 지점이므로 0을 반환하고, x + y = 2이면 2를 반환합니다. 후자는 (1,1), (2,0), (0,2)처럼 일반적인 재귀 규칙만으로는 올바르게 계산되지 않는 특수 경우이기 때문입니다.
(x, y)로 임시 pair 객체 temp를 만듭니다.
맵에 temp가 이미 존재하면 저장된 값을 즉시 반환하여 중복 계산을 방지합니다.
그렇지 않다면, solve(|x−1|, |y−2|)와 solve(|x−2|, |y−1|) 중 더 작은 값에 1을 더한 결과를 맵에 저장한 뒤 반환합니다.
메인 함수에서는 solve(|x|, |y|)를 호출해 최종 결과를 얻습니다.
C++ 구현 예제
아래 코드를 통해 구현 방식을 더 자세히 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
map < pair <int, int>, int > dp;
int solve(int x, int y){
if(x + y == 0) return 0;
if (x + y == 2) return 2;
pair <int, int> temp({x, y});
if(dp.count(temp)) return dp[temp];
return dp[temp] = min(solve(abs(x - 1), abs(y - 2)), solve(abs(x - 2), abs(y - 1))) + 1;
}
int minKnightMoves(int x, int y) {
return solve(abs(x), abs(y));
}
};
main(){
Solution ob;
cout << (ob.minKnightMoves(5, 5));
}
입력
5 5
출력
4
즉, 나이트가 [5, 5] 지점에 도달하기 위해 필요한 최소 이동 횟수는 4번입니다. 메모이제이션 덕분에 동일한 좌표에 대한 탐색이 반복되지 않으므로, 무한히 넓은 체스판에서도 효율적으로 답을 구할 수 있습니다.