문제 개요
배열 형태로 주어진 여러 좌표 점들이 있을 때, 모든 점을 방문하는 데 걸리는 최소 시간(초)을 구하는 문제입니다. 단, 다음 두 가지 조건이 있습니다.
- 1초마다 수직, 수평, 대각선 방향으로 한 칸씩 이동할 수 있습니다.
- 배열에 나타난 순서 그대로 점들을 방문해야 합니다.
예를 들어 점들이 [(1, 1), (3, 4), (-1, 0)]로 주어졌다면, 정답은 7입니다. 실제 최단 경로의 이동 순서는 다음과 같습니다.
(1, 1) → (2, 2) → (3, 3) → (3, 4) → (2, 3) → (1, 2) → (0, 1) → (-1, 0)
접근 방법
이 문제의 핵심은 체비셰프 거리(Chebyshev Distance) 개념입니다. 대각선 이동이 가능하기 때문에, 인접한 두 점 사이의 x좌표 차이와 y좌표 차이 중 더 큰 값이 곧 해당 구간을 이동하는 데 필요한 시간이 됩니다.
예를 들어 (1, 1)에서 (3, 4)로 이동할 때, x 차이는 2, y 차이는 3입니다. 대각선으로 이동하면 두 좌표를 동시에 줄일 수 있으므로, 필요한 시간은 max(2, 3) = 3초입니다.
따라서 전체 답은 다음과 같이 계산합니다.
- 연속된 두 점 사이의 x좌표 차이의 절댓값과 y좌표 차이의 절댓값을 구합니다.
- 두 값 중 최댓값을 선택합니다.
- 모든 구간의 값을 더하면 정답이 됩니다.
구현 예제
다음은 C++로 작성한 해결 코드입니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minTimeToVisitAllPoints(vector<vector<int>>& p) {
int ans = 0;
int n = p.size();
for(int i = 1; i < n; i++){
ans += max(abs(p[i][0] - p[i-1][0]), abs(p[i][1] - p[i-1][1]));
}
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> c = {{1,1},{3,4},{-1,0}};
cout << ob.minTimeToVisitAllPoints(c);
}입력
[[1,1],[3,4],[-1,0]]
출력
7
복잡도 분석
- 시간 복잡도: O(n) — 점의 개수만큼 한 번씩 순회합니다.
- 공간 복잡도: O(1) — 추가 메모리 없이 상수 공간만 사용합니다.
이처럼 각 구간의 이동 시간을 체비셰프 거리로 계산해 합산하면, 순서가 고정된 상황에서 모든 점을 방문하는 최소 시간을 효율적으로 구할 수 있습니다.