오늘은 맨해튼 거리에 대해서 기록하려고 한다.

먼가 맨해튼 거리라고 하면 뉴욕의 중심 맨해튼이 생각이 나면서 도시의 거리가 연상된다. 그러나 이 연상된 이미지가 맞다. 19세기의 수학자 헤르만 민코프스키가 고안한 용어로, 맨해튼 도시의 건물들이 사각형으로 붙어있는 모습과 닮아서 이름이 붙어졌다고 한다. 하지만 여기서의 거리는 거리(Street)가 아니라 거리(Distance)다. ㅎㅎ

 예를 들어 이러한 알고리즘 문제에서 활용할 수 있다.

1칸의 거리가 1인 2차원 평면 좌표에서, 특정 지점(t)이 다른 임의의 두 지점(p1, p2)에 대하여 거리를 각각 비교했을 때 더 가까운 지점을 선택하는 문제다.

이 맨해튼 거리 공식을 활용하지 않고 계산한다면 고려해야 하는 부분이 많아서 귀찮아진다. 하지만 아래 한 줄로 이 거리를 쉽게 구할 수 있다.

d = |x1 - x2| + |y1 - y2|

위의 공식처럼 두 좌표에 대해서 계산한다면 맨해튼 거리 d가 구해진다.

 최근에 풀었던 알고리즘 중 맨해튼 거리를 활용해서 풀었던 문제를 가져왔다. 카카오 인턴십 문제이며 프로그래머스 사이트에서 풀 수 있다.

아래는 실제 풀었던 소스 코드다.

#include <bits/stdc++.h>
 
using namespace std;
 
int getManhattanDist(pair<int, int> p1, pair<int, int> p2) {
    return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}
 
string solution(vector<int> numbers, string hand) {
    string answer = "";
    pair<int, int> leftThumb = {0, 3};
    pair<int, int> rightThumb = {2, 3};
    
    for (int i = 0 ; i < numbers.size(); i++) {
        int input = numbers[i];
        switch (input) {
            case 1: case 4: case 7: answer += "L"; leftThumb = {0, (input - 1) / 3}; break;
            case 3: case 6: case 9: answer += "R"; rightThumb = {2, (input / 3) - 1}; break;
            default:
                int y = (input == 0) ? 3 : (input / 3);
                int leftMahattanDist = getManhattanDist(leftThumb, {1, y});
                int rightMahattanDist = getManhattanDist(rightThumb, {1, y});
                if (leftMahattanDist < rightMahattanDist) {
                    answer += "L";
                    leftThumb = {1, y};
                } else if (leftMahattanDist > rightMahattanDist) {
                    answer += "R";
                    rightThumb = {1, y};
                } else {
                    if (hand == "left") {
                        answer += "L";
                        leftThumb = {1, y};
                    } else {
                        answer += "R";
                        rightThumb = {1, y};
                    }
                }
                break;
        }
    }
    
    return answer;
}

5~6번째 줄에서 맨해튼 거리를 구하는 함수를 볼 수 있고, 21~22번째 줄에서 맨해튼 거리를 구한 뒤 값을 비교해 문제를 풀어가는 걸 볼 수 있다. 해당 문제는 아래의 주소에서 직접 풀어볼 수 있다.

https://programmers.co.kr/learn/courses/30/lessons/67256