BOJ 12918 - 정리정돈 (+BOJ 2000솔)

2000번째 문제로 골라 풀게 되었다. 사실 원래 고른 문제는 https://www.acmicpc.net/problem/25950 이거였는데, 논문을 읽다 보니 며칠 안에 될 것 같지가 않아 그냥 북마크에 있던 적절히 재밌는 문제를 하나 골랐다.

 

점이 2개인 경우를 생각해보자. 점 $(a,b)$와 $(c,d)$가 있고, $a < 0 < c$라 하자. 이러면, $(a,b)$와 $(-c,d)$를 잇는 직선을 선대칭한 두 직선 위에 점을 각각 올려놓는 것이 최적이라는 사실을 알 수 있다. 이 경우 두 점의 이동거리의 합은 $\sqrt{(a+c)^2+(b-d)^2}$이다.

 

만약 $a$와 $c$의 부호가 같다면 어떻게 될까? 두 점의 이동거리의 합은 $\sqrt{(a+c)^2+(b-d)^2}$인데, 이는 두 점을 각각 y축 위로 이동시키는 비용인 $a+c$보다 크다. 따라서 x좌표의 부호가 같은 점끼리는 연결될, 즉 선대칭 관계를 가질 수 없다.

 

문제를 정리하면 다음과 같다. 점들을 x좌표의 부호를 기준으로 나눠 이분그래프를 만든 뒤 각 점은 반대쪽 점 중 하나와 $\sqrt{(a+c)^2+(b-d)^2}$의 비용으로 연결되거나, $|x|$의 비용으로 y축 위로 이동해야 한다. 기본적인 MCMF 형태인데, 추가적인 생각이 필요하다.

 

처음에 시도한 방법은 왼쪽 정점들 $l$에 대해서는 $(l, T, |x|)$의 간선을, 오른쪽 정점들 $r$에 대해서는 $(S, r, |x|)$의 간선을 추가한 것이었다. 당연히도, 이러면 저 간선들만 쓰는 것이 최적이라 답을 구할 수 없다.

 

나는 우선 최대 유량을 $l+r=n$이 아니라 $l$로 고정하려 했다. 이러면 위에서 언급한 두 종류의 간선 중 $(S, r, |a|)$들은 사용할 수 없다. 그러면 오른쪽 정점들을 y축 위로 옮기는 경우를 다시 고려해주어야 하는데, 이는 일단 모든 오른쪽 정점에 대해서 $|x|$의 합을 답에 더해준 뒤, 왼쪽과 오른쪽을 잇는 모든 간선의 비용 $\sqrt{(a+c)^2+(b-d)^2}$을 $\sqrt{(a+c)^2+(b-d)^2} - c$로 고쳐주면 된다. 즉, 일단 y축으로 옮긴 후 매칭이 되면 다시 풀어준다고 생각하는 것이다. 이러면 매칭되지 않은 왼쪽 정점들은 $(l, T, |x|)$ 간선을 반드시 사용하므로 고려해줄 수 있고, 매칭되지 않은 오른쪽 정점들은 비용의 성질에 의해 자동으로 계산된다.

 

모델링이 여러 가지 있는 것 같은데, 재미있는 문제이니 모두 풀어보셨으면 좋겠다.