yet another mst problem

1. 옮긴 점의 후보 위치

옮길 점을 $r$번 점이라고 하자. 나머지 점들의 집합을 $Q$라고 하고, 옮긴 뒤의 점을 $s$라고 하자.

최적해의 어떤 스패닝 트리를 고정하자. $s$와 인접한 점들의 집합을 $A$라고 하면, $s$의 위치에 따라 달라지는 비용은 다음과 같다.

$$\sum_{i \in A} |x_s-x_i| + \sum_{i \in A} |y_s-y_i|$$

두 합은 독립적이다. 절댓값 합은 중앙값에서 최소가 되므로, 최적의 $x_s$는 $A$에 속한 점 하나의 $x$좌표로, 최적의 $y_s$는 $A$에 속한 점 하나의 $y$좌표로 잡을 수 있다.

따라서 $Q$에 나타나는 $x$좌표와 $y$좌표의 모든 조합만 확인하면 충분하다. 후보 위치는 최대 $(N-1)^2$개이다. $N=1$이면 답은 $0$이다.

2. 남은 점들의 MST 하나만 사용하기

$Q$의 완전 그래프를 $G$라고 하고, 그 MST 하나를 $K$라고 하자. 후보 위치 $s$를 추가하면 $s$와 $Q$의 모든 점을 잇는 간선들이 새로 생긴다.

$G$의 모든 간선을 다시 사용할 필요는 없다. $K$의 간선과 $s$에서 나가는 간선만으로도 확장된 그래프의 MST를 만들 수 있다.

이를 보이기 위해, 확장된 그래프의 MST 가운데 $K$에 속하지 않는 기존 간선의 수가 최소인 것을 고르자. 그런 간선 $e$가 남아 있다고 하자. $K$에서 $e$의 양 끝점을 잇는 경로의 모든 간선 중 최댓값은 $e$의 가중치 이하이다. MST에서 $e$를 지워 생기는 절단을 이 경로가 가로지르므로, 그 절단을 가로지르는 $K$의 간선 $f$가 존재한다. $e$ 대신 $f$를 넣으면 가중치는 증가하지 않고 $K$ 밖의 기존 간선 수가 줄어 모순이다.

따라서 각 후보 위치에서는 정점이 $|Q|+1$개이고 간선이 $2|Q|-1$개인 그래프에 크루스칼 알고리즘을 적용하면 된다.

3. 새 간선을 선형 시간에 정렬하기

$K$의 간선은 옮길 점 $r$을 고정한 동안 변하지 않으므로 한 번만 정렬한다. 후보 위치를 $(X,Y)$라고 하자. $Q$의 점을 다음 네 영역으로 나눈다.

• $x_i \leq X$, $y_i \leq Y$: 거리는 $X+Y-(x_i+y_i)$이므로 $x_i+y_i$의 내림차순이다.
• $x_i \leq X$, $y_i > Y$: 거리는 $X-Y+(y_i-x_i)$이므로 $y_i-x_i$의 오름차순이다.
• $x_i > X$, $y_i \leq Y$: 거리는 $-X+Y+(x_i-y_i)$이므로 $x_i-y_i$의 오름차순이다.
• $x_i > X$, $y_i > Y$: 거리는 $-X-Y+(x_i+y_i)$이므로 $x_i+y_i$의 오름차순이다.

각 기준으로 점들을 미리 정렬한다. 한 후보 위치에서 각 정렬을 순회하며 해당 영역의 점만 남기면, $s$에서 나가는 간선은 네 개의 정렬된 열로 표현된다. 네 열과 정렬된 $K$의 간선을 동시에 병합하면서 크루스칼 알고리즘을 수행할 수 있다. 한 후보 위치의 계산량은 $O(N)$이다.

4. 전체 알고리즘

각 옮길 점 $r$에 대해 다음을 수행한다.

• $Q$의 맨해튼 완전 그래프에서 프림 알고리즘으로 MST $K$를 구한다.
• $Q$의 서로 다른 $x$좌표와 $y$좌표의 모든 조합을 후보 위치로 확인한다.
• 각 후보에서 $K$의 간선과 $s$에서 나가는 간선을 병합하여 크루스칼 알고리즘을 수행한다.

첫 번째 관찰에 의해 어떤 최적해의 옮긴 위치가 후보에 포함된다. 두 번째 관찰에 의해 그 후보의 MST는 $K$와 새 간선만으로 정확히 계산된다. 모든 옮길 점을 확인하므로 알고리즘이 구한 최솟값이 정답이다.

옮길 점 하나마다 후보가 $O(N^2)$개이고 후보 하나를 $O(N)$에 처리한다. 모든 옮길 점을 확인하므로 시간 복잡도는 $O(N^4)$이고, 메모리 복잡도는 $O(N^2)$이다.

Solution written by GPT5.6