오늘은 비교적 쉬운 문제를 가져와봤습니다. 하지만, 분명 배울점은 있는 문제이기에 소개해드립니다.
해당 문제는 2D 평면상의 여러 점들이 주어졌을 때, 모든 점들을 순서대로 방문하는데 필요한 최소 시간을 계산하는 것이 목표입니다.
각 이동에서는 상하좌우 또는 대각선으로 한 칸씩 이동할 수 있습니다.
이 문제에서 저는 처음에 유클리드 거리를 사용했습니다. 한 번 이동할 때마다 1초가 걸린다고 했으니, 그냥 거리계산으로 접근했습니다.
두 점이 같은 기울기에 있다면, 대각선으로 가는 것이 가장 최단이겠고, 그렇지 않다면, 유클리드 거리를 사용하는 것인 줄 알았었죠.
그래서, 처음 작성했던 코드는 아래와 같습니다.
class Solution(object):
def minTimeToVisitAllPoints(self, points):
answer = 0
for i in range(len(points)-1):
x1, y1 = points[i][0], points[i][1]
x2, y2 = points[i+1][0], points[i+1][1]
if x1-y1 == x2-y2: # 기울기가 같은 직선위의 두 점이라면,
answer += abs(x1-x2)
else: # 유클리드 거리
answer += int(sqrt(abs(x1-x2) ** 2 + abs(y1-y2) ** 2))
return answer
하지만, 여러가지 edge case가 존재할 것 같았습니다. 리트코드의 discussion을 보기 전에 스스로 테스트 케이스에 대해서 생각해봤는데요, 만약 위치가 (0,0) 이고, (3,4) 라는 두 개의 점이 있다고 가정해봅시다.
유클리드 거리의 계산법을 사용하게 되면, (0,0) 에서 (3,4) 까지 가는 가장 최단 거리는 5가 될 것입니다.
하지만, 여기선 오류가 있습니다. (0,0) 에서 (3,4) 까지 가는 최단 거리 방법은 "대각선 이동 3번과 수직 이동 1번으로 총 4번"이면 됩니다. 즉, 갈 수 있는 최단 거리는 4인 셈이죠.
Discussion에서는 많은 사람들이 "Chebyshev Distance"에 대해서 이야기를 했습니다. 이는 한국말로 하면 "체비셰프 거리" 입니다. 외국인들에게는 흔한 거리방법이지만, 우리에게는 '유클리드 거리'나 '맨하탄 거리' 만큼 익숙하지는 않을 듯 합니다.
체비셰프 거리는 모든 축에 따른 거리 중 최대를 구한 거리라고 할 수 있습니다. 체스 거리라고도 하며 체스판에서 왕이 한 점에서 다른 점으로 이동할 때 최소한으로 필요한 이동 횟수로 생각할 수 있죠. 이 개념은 기하학과 체스, 그리고 여러 최적화 문제에서 자주 사용되는데, 특히 가장 적은 수의 이동으로 도달할 수 있는 최단거리를 구하는 지금같은 문제에 유용하게 쓰입니다. 물론, 다차원 공간에서 두 점 사이를 계산하거나, 그리드 기반의 게임이나 애플리케이션에서도 경로 탐색을 최적화하는데 용이하겠죠.
Chebyshev Distance는 두 점 사이의 거리를 측정하는 방법 중 하나인 만큼 구체적으로, 두 점 (x1,y1) 과 (x2,y2) 사이의 거리는 max(|x2-x1|, |y2-y1|) 으로 계산합니다.
그렇다면, 왜 이렇게 계산 되는지 이해해봅시다.
- Chebyshev 거리는 두 점 간의 수평 또는 수직 거리와 같을 수 있습니다. 이는 두 점이 같은 행이나 열에 위치할 때 발생합니다.
- 두 점이 대각선 방향으로 떨어져 있을 때, Chebyshev 거리는 두 점 사이의 수평 또는 수직 거리 중 더 긴 거리와 동일합니다.
아까 문제에서의 예시를 가져와보겠습니다.
(1,1)과 (3,4) 사이의 수평 거리는 2, 수직 거리는 3 입니다. 체비셰피 거리는 따라서 3이 되겠죠.
(3,4)와 (-1,0) 사이의 수평 거리는 4, 수직 거리도 4 입니다. 체비셰피 거리는 따라서 4가 됩니다. 이렇게 같을 수도 있습니다.
아까 생각했던 예시인 (0,0) 에서 (3,4) 사이의 체비셰프 거리도 생각해보면, 유클리드 거리인 5가 아니라 4가 되는 것을 알 수 있죠.
체비셰프 개념을 적용한다면, 기울기가 같을 때와 같은 예외처리를 따로 해주지 않아도 됩니다.
최종 코드는 아래와 같습니다.
class Solution(object):
def minTimeToVisitAllPoints(self, points):
answer = 0
for i in range(len(points)-1):
x1, y1 = points[i][0], points[i][1]
x2, y2 = points[i+1][0], points[i+1][1]
answer += max(abs(x1-x2),abs(y1-y2)) # Chebyshev Distance
return answer
이상으로 Chebyshev Distance 과 관련한 1266. Minimum Time Visiting All Points 문제를 정리해봤습니다.
아래는 추가적인 내용입니다.
문제와 관련된 Discussion 에서 어떤 분이 아래와 같은 글을 남겼는데요,
이 질문을 해석해본다면, Facebook 면접에서 나왔던 알고리즘 문제의 변형에 관한 이야기 같습니다. 원래 문제는 2D 평면상의 점들을 주어진 순서대로 방문하는 데 필요한 최소 시간을 구하는 것이라면, 면접에서는 이 문제를 5분만에 빠르게 해결한 후, 변형된 문제를 제시받았다고 합니다.
새로운 문제는 점들을 특정 순서로 방문할 필요가 없으며, 어떤 순서로든 방문할 수 있을 때 모든 점을 방문하는 데 필요한 최소 시간을 구하는 것이었습니다. 필자는 이런 종류의 문제를 "최단 경로" 문제의 한 형태로 보는 것 같으신데, 기본적인 '최단경로' 알고리즘인 Dijkstra 나 A* 알고리즘을 생각했다고 합니다. 하지만, Dijkstra 나 A* 알고리즘으로는 해당 문제에 적용할 수 없어서 어려움을 겪었다고 합니다.
(※ Dijkstra 나 A* 알고리즘 단일 출발점에서 단일 도착점으로의 최단 경로를 찾는 데 효과적이지만, facebook이 저 분에게 내주신 follow up 문제는 다중 방문지점을 포함하는 문제이므로 다르게 접근해야 합니다.)
생각하는 방법으로는 "브르투 포스"(하지만, 너무 비효율적이겠죠.) 혹은 휴리스틱 방법(가장 가까운 이웃, 유전 알고리즘 등) 이나 DP(동적 프로그래밍 알고리즘)를 사용해서 해결책을 찾을 수 있겠습니다. 하지만, 이 또한 데이터 사이즈가 클 때는 비효율적일 수 있습니다.
그래서 Discussion 에 대한 답변 중에 어떤 분이 이렇게 답글을 해주셨습니다.
이 답변은 해당 질문자님의 문제에 답변을 해주고 있는데요, 이 분이 제시한 방법은 2가지입니다.
방법 1) 최소 신장 트리 (Minimum Spannig Tree, MST) 사용
- 이 접근법에서는 점들을 노드로 변환하고, 각 노드를 서로 연결하는 edge 의 가중치를 점들 사이의 Chebyshev 거리로 설정합니다.
- 그런 다음에, 이 그래프의 최소 신장 트리(MST)를 찾습니다. (MST 는 모든 노드를 최소한의 비용으로 연결하는 트리 구조입니다.)
- 이 방법의 시간 복잡도는 대략 O(n^2)로, 점의 수가 많아질수록 시간이 증가합니다.
방법 2) 그레이엄 스캔(Graham Scan) 알고리즘 사용
- 이 접근법에서는 먼저 가장 낮은 y좌표를 가진 점을 선택합니다.
- 그 다음 나머지 점들을 각 점이 만드는 각도에 따라 정렬합니다. 이는 그레이엄 스캔 알고리즘과 유사한 방식이며, 이 알고리즘은 보통 컨백스 헐(Convex Hull) 을 계산하는 데 사용됩니다.
- 마지막으로, 이런 점들을 시계 방향으로 순회하면서 경로를 정하는 방식입니다.
이 두 접근 방식 모두 follow up 문제에 대해 창의적이고 효과적인 해결책인 것 같습니다. 세상에는 정말 고수가 많다는 것을 다시 한번 깨닫습니다. 우리 모두 겸손하게 배웁시다!