문제 개요
두 개의 좌표 (x1, y1)과 (x2, y2)가 주어졌다고 가정해 보겠습니다. 토끼는 먹이 상자를 끌고 이동하며, 길이가 1인 밧줄로 상자에 연결되어 있습니다. 토끼는 상자를 자신이 서 있는 위치까지 당긴 후, 같은 방향으로 1칸 이동하여 길을 비켜줍니다. 또한 상자를 당기지 않은 상태에서도 오른쪽, 왼쪽, 위, 아래 어느 방향으로든 1칸씩 자유롭게 이동할 수 있으며, 이때 상자와 정확히 1칸 거리를 유지할 필요는 없습니다. 다만 상자를 다시 당기려면 반드시 상자 바로 옆 칸으로 이동해야 합니다.
토끼는 원하는 어느 지점에서든 출발할 수 있고, 어느 방향이든 1칸 이동하는 데 1초가 걸립니다. 우리가 구해야 할 것은 상자를 시작 위치에서 목표 위치까지 옮기는 데 필요한 최소 시간입니다.
예를 들어 입력이 x1 = 1, y1 = 1, x2 = 2, y2 = 2라면 출력은 4가 됩니다. 토끼가 (2, 1) 지점에서 출발한다고 생각해 보면, 먼저 (3, 1)에 있는 상태에서 상자를 (2, 1)로 당깁니다. 이후 상자를 당기지 않고 (3, 2)로 이동한 뒤 다시 (2, 2)로 이동하고, 마지막으로 (2, 3) 방향으로 이동하면서 상자를 (2, 2)로 당깁니다. 이 전체 과정에 4초가 걸립니다.
풀이 접근 방법
이 문제는 맨해튼 거리(Manhattan Distance) 개념을 활용하면 간단하게 해결할 수 있습니다. 핵심 규칙은 다음과 같습니다.
- x좌표와 y좌표 중 하나만 다른 경우(직선 이동): 필요한 시간은 |x2 − x1| + |y2 − y1| 입니다.
- x좌표와 y좌표가 모두 다른 경우(대각선 이동): 상자를 당기는 방향을 바꾸려면 토끼가 상자 주위로 재배치되어야 하므로 추가로 2초가 더 필요합니다. 즉, |x2 − x1| + |y2 − y1| + 2 입니다.
이를 의사 코드로 표현하면 다음과 같습니다.
s := 0
if x1 ≠ x2 and y1 ≠ y2, then:
s := |x2 - x1| + |y2 - y1| + 2
otherwise:
s := |x2 - x1| + |y2 - y1|
return sC++ 구현 예제
위 로직을 C++ 코드로 구현하면 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(int x1, int y1, int x2, int y2){
int s = 0;
if (x1 != x2 && y1 != y2)
s = abs(x2 - x1) + abs(y2 - y1) + 2;
else
s = abs(x2 - x1) + abs(y2 - y1);
return s;
}
int main(){
int x1 = 1;
int y1 = 1;
int x2 = 2;
int y2 = 2;
cout << solve(x1, y1, x2, y2) << endl;
}입력
1, 1, 2, 2
출력
4
마무리
이 문제의 핵심은 상자를 직선 방향으로만 당길 때는 단순 거리 계산으로 충분하지만, 방향을 꺾어야 하는 대각선 이동에서는 토끼가 상자 옆으로 자리를 잡는 추가 동작이 필요하다는 점입니다. 이를 +2초로 반영하면 O(1)의 시간 복잡도로 정답을 구할 수 있습니다.