1. 두 물체 사이의 거리는 어떻게 나타낼까요?
최단 거리를 찾는 문제를 풀다보면 보다 근본적인 궁금증이 생깁니다.
두 물체 사이의 거리는 무엇일까요?
아마 쉽게 두 물체를 연결한 직선의 길이를 떠올렸을 것입니다.
그러나 실제 현실에서는 조금 달라집니다.
서울에서 부산까지 차를 타고 가는데 필요한 거리는 서울과 부산을 직선으로 연결한 길이보다 길어질 것 입니다.
이렇게 거리를 나타낼 수 있는 서로 다른 두 가지 방법을 알아봅시다.
2. 유클리드 거리(Euclidean distance)
우리가 두 점 사이의 거리를 구하라고 했을 때 쉽게 떠올리는 방식입니다.
쉽게 생각해봅시다.
두 물체 사이에 가로 막는 것이 없고 두 물체 사이의 거리를 구하라고 하면 어떻게 하는게 제일 편할까요?
아마 줄자를 가지고 두 물체 사이의 거리를 재는 것이 가장 쉬운 방법일 것입니다.
이게 바로 유클리드 거리입니다.
만약 두 물체의 위치가 수직선 위의 좌표로 주어진다면 어떻게 해야할까요?
부호를 뺀 두 좌표 크기의 차이이므로 다음과 같이 나타낼 수 있습니다.
\(d = \left | x_{1} - x_{2}\right | \)
이번에는 평면 위의 이차원 좌표로 주어진다면 어떻게 해야할까요?
위와 같이 직각삼각형을 그리면 밑변은 x좌표의 거리, 높이는 y좌표의 거리가 되고, 두 점 사이의 거리는 빗변이 됩니다.
따라서, 피타고라스의 정리를 사용하면 다음과 같습니다.
\( d = \sqrt{(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}}\)
이번에는 입체 공간의 삼차원 좌표로 주어진다면 어떻게 해야할까요?
위와 같이 두 점을 꼭지점으로 하는 직육면체를 그리면 직각삼각형 두 개를 그릴 수 있습니다.
두 직각삼각형의 밑변과 높이는 두 점 사이에 x좌표의 거리, y좌표의 거리, z좌표의 거리로 다음과 같이 나타낼 수 있습니다.
\(d = \sqrt{(\sqrt{(x_{1}-x_{2})^{2}+(z_{1}-z_{2})^{2}})^{2}+(y_{1}-y_{2})^{2}}\)
정리하면, 다음과 같이 나타낼 수 있습니다.
\(d = \sqrt{(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}+(z_{1}-z_{2})^{2}}\)
3. 맨해튼 거리(Manhattan distance)
현실 세계에서는 유클리드 거리를 적용시키기 쉽지 않은 경우가 많습니다.
건물들이 격자 모양으로 밀집해있는 맨해튼 같은 도시에서 떨어져 있는 두 사람 사이의 거리를 단순히 유클리드 거리로 표현하면 문제가 생깁니다.
왜냐하면 두 사람이 만나기 위해서 건물을 뚫고 직선으로 이동하는 것은 불가능하기 때문입니다.
따라서 건물을 돌아가는 거리를 생각해야합니다.
이것이 바로 맨해튼 거리입니다.
맨해튼 거리도 1, 2, 3차원으로 나누어서 생각해봅시다.
1차원에서는 수직선과 수평으로 놓여있기 때문에 유클리드 거리와 같습니다.
\(d = \left | x_{1} - x_{2}\right | \)
2차원에서는 격자 모양으로 나아가는 여러 가지 경우는 결국 빨간색 화살표와 같이 x좌표의 거리와 y좌표의 거리로 평행이동 시켜서 나타낼 수 있습니다.
따라서 정리하면 다음과 같습니다.
\( d = \left | x_{1} - x_{2} \right | + \left | y_{1} - y_{2} \right | \)
마찬가지로 3차원에서도 맨해튼 거리를 생각해보면, 결국 빨간 화살표와 같이 x, y, z좌표 거리의 합이라는 것을 알 수 있습니다.
\( d = \left | x_{1} - x_{2} \right | + \left | y_{1} - y_{2} \right | + \left | z_{1} - z_{2} \right |\)
