두 개의 좌표 (x1, y1)과 (x2, y2)가 있다고 가정해 봅시다. 로봇은 현재 (x1, y1) 지점에 있으며, (x2, y2) 지점으로 이동하려고 합니다. 로봇은 한 번의 스텝(step)마다 인접한 8개의 칸 중 한 곳으로 이동할 수 있습니다(상, 하, 좌, 우 및 대각선 방향 포함). 우리가 구해야 할 것은 최종 위치에 도달하기 위해 필요한 최소 이동 횟수입니다.
문제 예시
예를 들어 입력이 다음과 같다고 해 보겠습니다.
x1 = 3; y1 = 4; x2 = 6; y2 = 1;
이 경우 출력은 3이 됩니다. 아래 그림처럼 대각선 방향을 활용하면 단 3번의 이동만으로 목적지에 도달할 수 있기 때문입니다.
풀이 아이디어
핵심은 로봇이 대각선으로도 이동할 수 있다는 점입니다. 대각선 이동 한 번으로 X축 거리와 Y축 거리를 동시에 1씩 줄일 수 있으므로, 필요한 최소 스텝 수는 두 축 방향 거리 차이 중 더 큰 값과 같습니다. 이는 체비셰프 거리(Chebyshev Distance)라고도 불립니다.
따라서 풀이 절차는 다음과 같습니다.
- X축 방향 거리 차이 |x2 − x1|를 계산합니다.
- Y축 방향 거리 차이 |y2 − y1|를 계산합니다.
- 두 값 중 최댓값(maximum)을 반환합니다.
return max(|x2 - x1|, |y2 - y1|);
C++ 구현 예제
아래 코드를 통해 실제 구현 방법을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(int x1, int y1, int x2, int y2){
return max(abs(x2 - x1), abs(y2 - y1));
}
int main(){
int x1 = 3;
int y1 = 4;
int x2 = 6;
int y2 = 1;
cout << solve(x1, y1, x2, y2) << endl;
}입력
3, 4, 6, 1
출력
3
복잡도 분석
이 풀이는 단순히 두 값의 절댓값 차이를 계산하고 최댓값을 반환하기만 하면 되므로, 시간 복잡도는 O(1)입니다. 추가적인 메모리 사용 없이 상수 시간 안에 답을 구할 수 있는 매우 효율적인 알고리즘입니다.