문제 개요
2차원 격자 위에 나무 한 그루, 다람쥐 한 마리, 그리고 여러 개의 견과류가 놓여 있습니다. 각 위치는 격자의 셀(cell) 좌표로 표현되며, 목표는 다람쥐가 모든 견과류를 하나씩 모아 나무 아래에 옮겨놓을 때 필요한 최소 이동 거리를 구하는 것입니다.
다람쥐에게는 두 가지 제약 조건이 주어집니다.
- 한 번에 최대 한 개의 견과류만 가질 수 있습니다.
- 상, 하, 좌, 우 네 방향으로 인접한 셀로만 이동할 수 있으며, 거리는 이동 횟수, 즉 맨해튼 거리(Manhattan Distance)로 측정합니다.
예를 들어 높이가 5, 너비가 7이고, 나무의 위치가 [2,2], 다람쥐의 위치가 [4,4], 견과류의 위치가 [[3,0], [2,5]]라면 정답은 12가 됩니다.
문제 해결 접근법
이 문제의 핵심 아이디어는 의외로 단순합니다. 모든 견과류에 대해 "나무 → 견과류 → 나무"의 왕복 거리를 전부 더하면 기본적인 총 이동 거리가 됩니다. 하지만 첫 번째 견과류를 가져갈 때만큼은 굳이 나무에서 출발할 필요 없이 다람쥐의 현재 위치에서 바로 출발할 수 있습니다. 따라서 어느 견과류를 먼저 가져가느냐에 따라 절약되는 거리가 달라지며, 절약 거리가 가장 큰 견과류를 첫 대상으로 삼으면 됩니다.
구체적인 풀이 단계는 다음과 같습니다.
- calc() 함수 정의 — x1, y1, x2, y2를 입력받아 두 지점 사이의 맨해튼 거리 |x1 − x2| + |y1 − y2|를 반환합니다.
- minDistance() 함수 정의 — 높이(height), 너비(width), 나무 위치 배열(tree), 다람쥐 위치 배열(sq), 견과류 위치 2차원 배열(nuts)을 매개변수로 받습니다.
- 누적 거리 ret은 0으로, 최대 절약량 maxDiff는 음의 무한대(-∞)로 초기화합니다.
- 모든 견과류 i에 대해 다음을 반복합니다.
- dist := 나무와 i번째 견과류 사이의 거리를 계산합니다.
- ret := ret + 2 × dist (왕복 거리를 누적합니다.)
- maxDiff := max(maxDiff, 2 × dist − (dist + 다람쥐와 해당 견과류 사이의 거리)) — 이 값이 바로 해당 견과류를 첫 번째로 가져갈 때 절약되는 거리입니다.
- ret − maxDiff를 반환합니다. 이것이 곧 최소 이동 거리입니다.
이 알고리즘의 시간 복잡도는 견과류 개수를 N이라 할 때 O(N)이며, 추가 메모리 없이 상수 공간 O(1)로 해결할 수 있습니다.
C++ 구현 예제
아래 코드를 통해 동작 방식을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int calc(int x1, int y1, int x2, int y2){
return abs(x1 - x2) + abs(y1 - y2);
}
int minDistance(int height, int width, vector<int>& tree, vector<int>& sq, vector<vector<int>>& nuts) {
int ret = 0;
int maxDiff = INT_MIN;
for (int i = 0; i < nuts.size(); i++) {
int dist = calc(tree[0], tree[1], nuts[i][0], nuts[i][1]);
ret += 2 * dist;
maxDiff = max(maxDiff, 2 * dist - (dist + calc(nuts[i][0], nuts[i][1], sq[0], sq[1])));
}
return ret - maxDiff;
}
};
main(){
Solution ob;
vector<int> v = {2,2}, v1 = {4,4};
vector<vector<int>> v2 = {{3,0}, {2,5}};
cout << (ob.minDistance(5,7,v, v1, v2));
}
입력
5, 7, {2,2},{4,4}, {{3,0}, {2,5}}
출력
12
결과 분석
나무 [2,2]에서 견과류 [3,0]까지의 거리는 3, 견과류 [2,5]까지의 거리 역시 3입니다. 모든 견과류를 나무 기준 왕복으로 옮기면 3 × 2 + 3 × 2 = 12가 됩니다.
이제 첫 이동을 다람쥐 위치에서 시작할 때의 절약량을 살펴보겠습니다. 절약량은 "나무→견과류 거리 − 다람쥐→견과류 거리"로 계산됩니다.
- 견과류 [2,5]: 3 − 3 = 0
- 견과류 [3,0]: 3 − 5 = −2 (오히려 손해)
따라서 최대 절약량 maxDiff는 0이 되고, 최종 답은 12 − 0 = 12입니다. 다람쥐가 [2,5]를 먼저 가져간 뒤 [3,0]을 처리하는 것이 최적 경로임을 알 수 있습니다.