두 값 r과 c가 주어졌다고 가정해 봅시다. 무한히 큰 체스판의 좌표 (0, 0)에 체스 나이트가 처음 놓여 있을 때, 목표 위치 (r, c)에 도달하기 위해 필요한 최소 이동 횟수를 구하는 것이 이번 문제의 목표입니다.
나이트는 체스 규칙과 동일하게 움직입니다. 즉, 가로로 두 칸 그리고 세로로 한 칸 이동하거나, 반대로 세로로 두 칸 그리고 가로로 한 칸 이동합니다.
예를 들어 입력이 r = 6, c = 1이라면 출력은 3이 됩니다. 아래 그림에서 빨간색은 시작 위치, 초록색은 최종 목적지, 노란색은 중간 경유 지점을 나타냅니다.
문제 해결 접근 방법
이 문제는 BFS(너비 우선 탐색) 없이도 수학적 공식을 활용하면 상수 시간 O(1) 안에 해결할 수 있습니다. 해결 과정은 다음과 같습니다.
- r이 c보다 작으면 두 값을 서로 교환(swap)하여 r ≥ c 조건을 만족시킵니다.
- (r, c)가 (1, 0)과 같다면 특수 케이스로 3을 반환합니다.
- (r, c)가 (2, 2)와 같다면 역시 특수 케이스로 4를 반환합니다.
- delta := r - c 로 설정합니다.
- c > delta 인 경우, delta - 2 * ((delta - c) // 3) 을 반환합니다.
- 그렇지 않은 경우, delta - 2 * ((delta - c) // 4) 를 반환합니다.
일반적인 경우 나이트의 최소 이동 횟수는 대각선 방향 이동(delta)을 기준으로 계산되며, 대각선에서 벗어난 거리(c와 delta의 차이)에 따라 3 또는 4로 나눈 몫을 이용해 보정하는 방식입니다. (1, 0)과 (2, 2)는 이 공식이 적용되지 않는 예외적인 위치이므로 별도로 처리해야 합니다.
아래 예시 코드를 통해 더 자세히 이해해 보겠습니다.
예제 코드
class Solution:
def solve(self, r, c):
if r < c:
r, c = c, r
if (r, c) == (1, 0):
return 3
if (r, c) == (2, 2):
return 4
delta = r - c
if c > delta:
return delta - 2 * ((delta - c) // 3)
else:
return delta - 2 * ((delta - c) // 4)
ob = Solution()
r = 6
c = 1
print(ob.solve(r, c))
입력
6, 1
출력
3
위 코드는 좌표 (0, 0)에서 출발한 나이트가 (6, 1)에 도달하기 위해 정확히 3번의 이동이 필요함을 보여줍니다. 이 알고리즘은 모든 좌표에 대해 일정한 시간 복잡도 O(1)로 동작하므로, 매우 큰 좌표 값이 입력되더라도 효율적으로 답을 구할 수 있다는 장점이 있습니다.