맨해튼 거리가 최소가 되는 지점 찾기

▶ 유형

• 맨해튼 거리(Manhattan Distance)는 도시 블록을 따라 이동하는 거리를 계산하는 방식이다.
• 수학에서의 거리 공식이랑은 다른데, |x1 - x2| + |y1 - y2| 로 두 점 사이의 x좌표 차이의 절댓값과 y좌표 차이의 절댓값의 합을 맨해튼 거리라고 부른다.
• 즉 격자형 구조에서의 최단 거리를 구하면 되는 거니까 좌표평면이나 대각선을 고려하지않는 상황에서 유용한 수식이라고 생각하면 된다.
• 근데 이걸 여러 점들 사이에서 맨해튼 거리 최소 합을 구하려면 중앙값을 선택하면 된다.

▶ 전략

1차원, 2차원으로 나눠서 보겠다.

 

1차원에서 여러 점들로부터의 맨해튼 거리 합이 최소가 되는 지점이 중앙값인 이유를 알아보자.

수평선에 n개의 점 x₁, x₂, ..., xₙ이 있을 때, 거리 합을 생각해본다면 

• p가 어떤 점 xᵢ보다 작으면: -1 기여
• p가 어떤 점 xᵢ보다 크면: +1 기여

라고 볼 수 있다. 그래서 결국 최적값을 찾기 위해서는 기준 점을 중심으로 작은 점들의 개수, 큰 점들의 개수가 같은 지점에 놔야하는데, 이 말은 곧 중앙값이라는 얘기가된다.

 

다시 말하자면, 수평선에서

중앙값에서 왼쪽으로 이동할 경우 왼쪽 점들과의 거리는 줄지만, 오른쪽 점들과의 거리가 더 많이 증가하고
중앙값에서 오른쪽으로 이동: 오른쪽 점들과의 거리는 줄지만, 왼쪽 점들과의 거리가 더 많이 증가한다.

그래서 중앙값이 이 때 최적점이 되는 것이다!

 

그럼 2차원으로 가보자

2차원은 수평선이 단순히 2개 있다고 생각하면 된다. 곧 x축과 y축이 독립적으로 존재하고, 각각의 축을 기준으로 1차원 맨해튼 거리 최적점 찾듯 하면 된다.

 

즉 x좌표의 중앙값과 y좌표의 중앙값이 만나는 점이 전체 최적해라고 생각할 수 있다. 

 

바로 문제 풀어보자.

 

https://www.acmicpc.net/problem/18310

1차원 맨해튼 거리 합 최적점을 찾는 문제다.

 

난 처음에 이렇게 작성했다가 바로 시간초과가 났다.

public static void go() {
    int[] target = new int[n];
    for (int i = 0; i < n; i++) {
        target[i] = point[i];
    }
    Arrays.sort(target);
    int min = Integer.MAX_VALUE;
    int minT = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int center = (target[j] + point[i]) / 2;
            int dist = 0;
            for (int k = 0; k < n; k++) {
                int d = Math.abs(point[k] - center);
                dist += d;
            }
            if (min > dist) {
                min = dist;
                minT = center;
            }
            // System.out.println("dist: " + dist + " minT: " + minT + " center: " + center);
            // System.out.println();
        }
    }
}

진짜 완전탐색 방식으로 푼건데 이렇게 하면 보다시피 O(n^3)이다.

n이 20만이라 절대 이렇게 하면 안된다.

 

수평선 최적점을 생각하며 다시 풀면 아래와 같이 짧은 풀이가 완성된다.

public static void go() {
    Arrays.sort(point);
    System.out.println(point[(n - 1) / 2]);
}

 

이걸 2차원으로 들고 가면 아래 문제가 된다.

https://www.acmicpc.net/problem/1090

처음에 중앙값이 항상 최적인 이유를 모르고, 주어진 점을 활용해서 거리합을 구했다. 이렇게하면 첫번째 예시에서 0 2 4 6이 나오며 틀린 답만 내놓는다.

 

그래서 x 축, y 축을 분리해 각 좌표를 떼어내어 조합해야된다.

처음 작성할 때 중앙값 비교를 생각하지 못해서 계속 틀렸다.

public static void go() {
    for (int k = 1; k <= n; k++) {
        // k일때 최소거리합
        int res = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int centerX = checker[i][0]; // 원 대상의 X
                int centerY = checker[j][1]; // 비교 대상의 Y

                int[] dist = new int[n];
                for (int p = 0; p < n; p++) {
                    dist[p] = Math.abs(checker[p][0] - centerX) + Math.abs(checker[p][1] - centerY);
                }
//                    System.out.println(Arrays.toString(dist));
                Arrays.sort(dist);

                int sum = 0;
                for (int d = 0; d < k; d++) {
                    sum += dist[d];
                }

                res = Math.min(res, sum);
            }
        }
        sb.append(res).append(" ");
    }
}

원대상의 X좌표, 비교 대상의 Y좌표를 기준으로 해서 맨해튼 거리를 구하며 k 만큼의 합을 계속 만들어가면 되는 문제다. 나는 난이도를 모두 가리고 풀기 때문에 이게 플레라는 걸 알고 좀 놀랐다.

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요!