PS Featured

[PS] BOJ 27297 / 맨해튼에서의 모임

Minjun Kim

30 Nov 2025 • 2 min read

Thumbnail: Photo by Luca Bravo (Unsplash)

문제 링크: https://www.acmicpc.net/problem/27297

정렬을 활용해 중앙값을 찾는 문제입니다.

풀이

맨해튼 거리

N차원의 두 점 $A = (A_1, A_2, \cdots, A_N)$와 $B = (B_1, B_2, \cdots, B_N)$ 사이의 맨해튼 거리 $d_AB$는 다음과 같습니다.

$d_{AB} = \sum_{i = 1}^{N} \left\vert A_{i} - B_{i} \right\vert$

def distance(point1, point2):
    dist = 0
    for i in range(N):
        dist += abs(point1[i] - point2[i])
    return dist

N차원의 두 좌표 사이의 맨해튼 거리를 계산하는 함수

맨해튼 거리는 흔히 택시 거리로도 알려져 있습니다.

페르마 포인트(중간 지점) 찾기

우리가 찾고자 하는 지점은 주어진 모든 점으로부터의 거리 합이 최소가 되는 지점입니다.

맨해튼 거리의 계산식을 보면, 각 차원의 좌표 차가 독립적으로 계산되는 것을 알 수 있습니다. 따라서, 각 좌표축에서의 중앙값을 찾으면 모든 점으로부터의 거리 합을 최소로 만들 수 있습니다.

각 좌표축에서의 중앙값은 정렬을 통해 구할 수 있습니다. 좌표는 $M$개 주어지므로, $M \over 2$번째 원소가 중앙값이 됩니다. 만약 $M$이 짝수일 경우 중앙값이 2개 존재하지만, 어느 것을 골라도 결과는 같습니다.

pos = [0] * N
for i in range(N):
    coords = sorted(points, key=lambda x: x[i])
    pos[i] = coords[(M - 1) // 2][i] # 배열의 인덱스는 0 ~ M-1이므로, M-1의 절반이 중앙값의 인덱스이다.

각 좌표축의 중앙값을 구해 페르마 포인트 찾기

전체 코드

input = open(0).readline
N, M = map(int, input().split())

def distance(point1, point2):
    """맨해튼 거리 계산 공식
    Arguments:
        point1 (Iterable[int]): 거리를 계산할 좌표
        point2 (Iterable[int]): 거리를 계산할 좌표
    """
    dist = 0
    for i in range(N):
        dist += abs(point1[i] - point2[i])
    return dist

# 1. 좌표 입력 받기
points = list(tuple(map(int, input().split())) for _ in range(M))

# 2. 정렬을 통해 각 차원별 중앙값 구하기
pos = [0] * N
for i in range(N):
    coords = sorted(points, key=lambda x: x[i])
    pos[i] = coords[(M - 1) // 2][i] # 배열의 인덱스는 0 ~ M-1이므로, M-1의 절반이 중앙값의 인덱스이다.

# 3. 모든 좌표로부터 페르파 포인트로의 거리의 합 계산하기
dist = 0
for i in range(M):
    dist += distance(points[i], pos)

print(dist)
print(*pos)

solution.py