모든 좌표까지 맨해튼 거리 합이 최소가 되는 위치를 구하는 방법

1. 모든 점까지 맨해튼 거리의 합이 최소가 되는 점의 위치?

 

m차원의 n개의 점들 $P_{1}(x_{11},x_{12},...,x_{1m}), ... P_{n}(x_{n1},x_{n2},...,x_{nm})$에 대하여,

 

이들까지 맨해튼 거리의 합이 최소가 되는 점 X의 좌표를 구하라고 한다면, 어떻게 구할 수 있을까?

 

정답은 n개의 점들을 1,2,...,m차원의 좌표 값에 대하여 정렬한 다음, 중앙값에 해당하는 점의 좌표 $P_{median}$이 된다.

 

직관적으로 쉽게 눈치챌 수 있기는 한데, 왜 그런지 생각해보자.

 

 

2. 증명

 

먼저 점들의 좌표가 합에 서로 영향을 주지 않는다는 점을 관찰하자.

 

예를 들어 (3,5), (4,2), (5,1)에 대하여 (x,y)까지 맨해튼 거리의 합은..

 

$|x-3| + |y-5| + |x-4| + |y-2| + |x-5| + |y-1| = |x-3| + |x-4| + |x-5| + |y-5| + |y-2| + |y-1|$

 

즉 맨해튼 거리의 합은 각 차원의 좌표 합끼리 나눌 수 있다.

 

(x1,y1),(x2,y2),...,(xn,yn)에 대하여..

 

$$S = \sum_{i = 1}^{n}|x - x_{i}| + \sum_{i=1}^{n}|y - y_{i}|$$

 

그러므로 하나의 차원에 대해 최솟값을 생각한다면, 나머지 차원에 대해서도 동일하게 생각할 수 있다.

 

즉, 이제 문제는 $f(x) = \sum_{i=1}^{n}|x - x_{i}|$가 최소가 되는 $x$는 무엇인가?

 

 

마찬가지로 합이 서로 영향을 주지 않기 때문에 일반성을 잃지 않고 $x_{1} < x_{2} < ... < x_{n}$으로 정렬된 상태를 가정할 수 있다.

 

정렬한 상태에서 어떤 m에 대하여, $x_{m} \leq x < x_{m+1}$이 성립하는 x에 대하여...

 

$x_{1},x_{2},x_{3},...,x_{m}$는 x보다 작거나 같으므로 $|x - x_{i}| = x - x_{i}$

 

$x_{m+1},x_{m+2},...,x_{n}$은 x보다 크므로, $|x - x_{i}| = x_{i} - x$

 

그러므로, $$f(x) = \sum_{i=1}^{m}(x-x_{i}) + \sum_{i = m+1}^{n}(x_{i} - x)$$

 

식을 계산해보면... $$f(x) = mx - (nx - mx) + \sum_{i = m+1}^{n}x_{i} - \sum_{i = 1}^{m} x_{i} = (2m-n)x + \sum_{i=m+1}^{n}x_{i} - \sum_{i=1}^{m}x_{i}$$

 

x에 대해 미분하면, f'(x) = 2m-n이다.

 

그러므로, f'(x) > 0인 2m > n이면 f(x)가 증가하고 f'(x) < 0인 2m < n이면 f(x)가 감소하고 n = 2m에서 극값을 가진다.

 

이 말이 무슨말일까?

 

m < n/2이면, f(x)가 감소하다가 m = n/2에서 극값을 가지고 m > n/2이면 f(x)가 증가하는 형태이다.

 

즉, m = n/2에서 f(x)가 최솟값을 가진다. 

 

구체적으로 n = 2m-1이라고 하자. 

 

n = 1 >>> m = 1

 

n = 3 >>> m = 2

 

n = 5 >>> m = 3

 

n = 7 >>> m = 4

 

...

 

예를 들어 n = 7인 경우 n/2 = 3.5인데, m으로 3.5보다 작은 값 m = 3을 고른다면, $x_{3} \leq x < x_{4}$인 x에 대해서는 f(x)가 감소한다.

 

하지만 m > 3.5보다 큰 m = 4를 고르면 $x_{4} \leq x < x_{5}$의 x에 대해서는 f(x)가 증가한다.

 

그러므로 $x = x_{4}$에서 f(x)가 최솟값을 가진다고 이해할 수 있다.

 

 

이번엔 n = 2m으로 짝수라고 해보자.

 

n = 2 >> m = 1

 

n = 4 >> m = 2

 

n = 6 >> m = 3

 

n = 8 >> m = 4

 

...

 

예를 들어 n = 8인 경우 n/2 = 4인데, m으로 4보다 작은 값 m = 3에 대하여... $x_{3} \leq x < x_{4}$인 x에 대해서는 f(x)가 감소한다.

 

그러다가 m = 4를 고르면 $x_{4} \leq x < x_{5}$인 x에 대해서 f(x)가 0이 된다. 

 

그리고 m = 5를 고르면 $x_{5} \leq x < x_{6}$인 x에 대해서는 f(x)가 증가하기 시작한다.

 

그러므로 $x_{4} \leq x < x_{5}$인 모든 x에 대하여 f(x)가 최소가 된다.

 

즉 n = 2m-1로 홀수이면 $x_{m}$으로 유일한 점이 존재하지만,

 

n = 2m으로 짝수이면 $x_{m} \leq x < x_{m+1}$인 모든 x에 대해 최소가 될 수 있다.

 

 

 

3. 연습문제1

 

14400번: 편의점 2 (acmicpc.net)

14400번: 편의점 2

 

 

4. 풀이

 

n이 10만이라 위의 사실을 모르면 단순하게 풀기 어렵다..

 

위 알고리즘에 따라 x,y좌표 각각 x_points, y_points 배열 각각에 좌표들을 모아둔다.

 

x_points, y_points를 모두 정렬한다.

 

그리고 중앙에 있는 좌표 x_points[n//2], y_points[n//2]가 모든 맨해튼 거리의 합을 최소로 하는 점의 좌표이므로 이를 구한다.

 

x_points,y_points를 다시 순회하여 x_points[n//2], y_points[n//2]의 맨해튼 거리의 합을 구한다.

 

from sys import stdin

n = int(stdin.readline())

x_points = []
y_points = []

for _ in range(n):
    
    x,y = map(int,stdin.readline().split())

    x_points.append(x)
    y_points.append(y)

x_points.sort()
y_points.sort()

x,y = x_points[n//2],y_points[n//2]

answer = 0

for i in range(n):

    answer += abs(x_points[i] - x)
    answer += abs(y_points[i] - y)    

print(answer)

 

 

증명하다가 느낀게 n = 7이면 7//2 = 3인데... 위에서 보인거라면 $x_{4}$에서 최소여야하는데??

 

라고 생각했는데...

 

배열은 제로 인덱스라서 x_points[3]이 $x_{4}$잖어..

 

 

 

5. 연습문제2

 

27297번: 맨해튼에서의 모임 (acmicpc.net)

27297번: 맨해튼에서의 모임

 

정답이 여러개일 경우 아무거나 하나만 출력하라고 나와있는데 위에서 보인대로,

 

점의 개수가 짝수일 경우 중앙의 점 $x_{m}$, $x_{m+1}$로 이은 선분 위의 모든 점 $x_{m} \leq x < x_{m+1}$에 대해 답이 될 수 있기 때문이다.

 

 

 

6. 풀이

 

위의 문제는 2차원이지만 이번 문제는 n차원에서 모든 맨해튼 거리의 합이 최소가 되는 점의 좌표를 구하는 것이다.

 

마찬가지로 동일하게 각 차원마다 좌표 배열 points[0], points[1], ... , points[n-1]을 모두 모아둔다.

 

points를 순회해서 얻은 points[0], points[1],..., points[n-1]에 대하여...

 

points[i] = point라 하고 이들을 정렬한다.

 

point에는 m개의 점 좌표가 들어있으므로 중앙의 좌표는 point[m//2]이다.

 

실제 최소가 되는 점의 좌표를 구해야하므로 point[m//2]도 따로 저장해두고, 다시 point를 하나하나 순회해서 

 

맨해튼 거리 합을 누적시켜준다.

 

from sys import stdin

n,m = map(int,stdin.readline().split())

points = [[] for _ in range(n)]

for _ in range(m):
    
    p = list(map(int,stdin.readline().split()))

    for i in range(n):
        
        points[i].append(p[i])

fermat = []

answer = 0

for point in points:
    
    point.sort()

    fermat.append(point[m//2])

    for p in point:
        
        answer += abs(p - fermat[-1])

print(answer)
print(' '.join(map(str,fermat)))