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|)\) 간선을 반드시 사용하므로 고려해줄 수 있고, 매칭되지 않은 오른쪽 정점들은 비용의 성질에 의해 자동으로 계산된다.

 

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