SCPC 2016 2차예선 5번 풀이. 난민촌

문제 설명(요약)

평면 위에 N개의 점 (x_i, y_i)가 있고, N개의 자연수 a_i가 주어져 있다. 가상의 평균점 C(x_c, y_c)와 a_i들의 순열 a_p(1), ..., a_p(N)을 잘 정해 다음 식을 최소화하면 그 최솟값은 얼마인가?

제약 조건: N <= 20

실행 조건: 테스트 케이스 20개에 대한 실행 시간 총합이 10초 이내. 메모리 256MB 이내.

부분문제 1 풀이

우선, a_i들의 순열 a_p(1), ..., a_p(N)이 정해지면 평균점을 쉽게 구할 수 있다. N <= 10이므로 완전탐색으로 해결 가능하다.

평균점을 구하는 구체적인 방법은 다음과 같다. a_p(i)를 z좌표로 생각하고, xy-평면에서 그만큼 솟아올라있다고 생각해보자. 그러면 이 점들을 덮을 수 있는 최소 크기의 정사각뿔(단, 정팔면체의 위쪽 절반과 닮음이면서 밑면의 대각선이 좌표축과 평행한 것)을 생각할 수 있다. 이 정사각뿔의 중심점이 바로 이 순열에 대한 최적의 가상의 평균점이며, 이때 주어진 식의 값은 정사각뿔의 반지름(밑면의 한 꼭지점에서 밑면의 중심점까지의 거리)과 같다.

정사각뿔은 어떻게 구할 수 있을까? 모든 p(i)값이 0이어서 2차원 문제로 환원되는 경우를 생각해보자. 이 경우는 기울기가 ±45도인 두 직선을 움직이면서 모든 점을 겨우 포함하는 최소 경계를 찾으면 된다. 구체적인 구현을 할 때에는 x+y와 x-y값의 최댓값과 최솟값의 차이를 구해 둘 중 큰 것을 택하면 마름모의 지름(반지름의 2배)이 된다.

3차원에서는 어떻게 할까? ±x ±y + z = k로 놓고 각각의 부호 조합(4가지)에 대해 k값의 최댓값을 구한 다음 (k_+x+y+z + k_-x-y-z) / 2, (k_+x-y+z + k_-x+y+z) / 2 중 큰 것을 택하면 정사각뿔의 반지름이 된다.

이렇게 하면 시간복잡도 O(N! * N)으로 N <= 10인 부분문제 1을 해결할 수 있다. 하지만 부분문제 2를 해결하기 위해서는 아이디어가 필요하다.

부분문제 2 풀이

정말 완전 탐색을 해야 할까? 이 질문에 답하기 위해, 앞서와는 반대로 순열 대신 가상의 평균점 C(x_c, y_c)가 먼저 고정된 경우를 생각해보자. 이때의 최적 순열은 택시거리가 C에서 먼 점일수록 더 작은 값이 들어가 균형을 맞추는 순열이다. 왜냐면 그렇지 않다고 하면 이것이 위반된 위치를 i, j라고 할 때 i와 j에 할당된 자연수를 서로 바꾸어도 그 해가 더 좋아질 수 있을 뿐 나빠질 수는 없기 때문이다. 따라서 가상의 평균점이 고정되었다면 고려할 순열은 하나뿐이다.

그런데 이러한 최적 순열을 모든 평균점에 대해 전부 나열하더라도 가능한 순열 N!개에 비해서 훨씬 적다. 즉 부분문제 1의 풀이방법은 고려할 필요가 없는 순열들을 고려하느라 시간을 낭비한다는 것이다.

그렇다면 고려해야 할 순열의 구체적인 개수는 어떻게 될까? 이를 따지려면 최적 순열이 바뀌는 지점을 생각해야 한다. 직관적으로 봤을 때, 어떤 가상의 평균점 C에서 아주 미소한 양 (dx, dy)만큼 움직였다고 해도 순열이 그렇게 변할 것 같지는 않다. 그러므로 평면은 같은 최적 순열을 공유하는 몇 개의 영역으로 분할된다. 이때 최적 순열은 평균점 C에서 각 점까지의 택시거리에 따라 결정된다고 했으므로, 최적 순열이 변하는 경계는 서로 다른 어떤 두 점까지의 택시거리가 같은 점이어야만 한다.

점이 N개이므로 이러한 경계는 _NC₂ = O(N²)개 존재한다. 또한 이 경계에 의해 분할된 영역은 대개 서로 다른 두 경계가 만나는 교점과 인접하고 있다. 경계의 기울기는 수직, 수평 또는 ±45도이므로 교점 근방의 8개의 방위(pi/8, 3*pi/8, ..., 15*pi/8)만 고려하면 충분하다. 그러면 O(N⁴)개의 교점을 고려하는 것이다. 단 이렇게만 하면 서로 다른 두 경계가 만나는 교점과 인접하지 않는 영역이 고려되지 않으므로, 모든 경계의 각 영역에 점을 추가로 하나씩 찍어주어야 한다.

이때 주의할 점은 택시거리의 등거리 경계는 유클리드 거리와 달리 굉장히 특이하다는 점이다. 유클리드 거리에서는 모든 등거리 경계가 직선이지만, 택시거리에서는 예외가 하나 있다. 바로 두 점의 x좌표 차이와 y좌표 차이가 같은 경우다. 이때는 아래 그림처럼 선뿐만이 아닌 영역과 선의 조합으로 등거리 경계가 형성되므로 주의해야 한다. 이 경계를 표현하려면 5개의 선분 또는 반직선이 필요하다.

(Interactive Demo는 다음 링크 참조: http://demonstrations.wolfram.com/SetOfPointsEquidistantFromTwoPointsInTaxicabGeometry/)

이렇게 얻은 후보 점들을 모아서 최적 순열을 구하면 O(N⁴)개밖에 되지 않으므로 제한 시간 내에 충분히 모두 시도해볼 수 있다. 즉, 각각의 영역을 대표하는 대표 점들을 모아 최적 순열을 구한 다음, 역으로 최적 순열이 주어졌다고 가정하고 최적의 평균점을 찾는 것이다. 최종 시간복잡도는 O(N⁵ * C)인데, 이때 상수 C가 꽤 크므로 일부러 따로 썼다. 물론 시간 내 해결에 문제될 정도는 아니다.