[일반] 백준 행성 터널 질문..

[익명(211.36)]

https://www.acmicpc.net/problem/2887

Baekjoon Online Judge

행성을 x,y,z 기준으로 정렬해 나오는 간선만 사용해도 최소비용을 얻을 수 있다는 게 증명 가능하다는데 증명된 블로그도 없고 해서 ..

[Bubbler(bubbler)]

일단 최소 스패닝 트리를 구해야 하는데, (x1,y1,z1)과 (x2,y2,z2)를 연결하는 비용 min(|x1-x2|, |y1-y2|, |z1-z2|) 간선이 있는 그래프에서의 mst는 비용이 각각 |x1-x2|, |y1-y2|, |z1-z2|인 간선 3개가 있는 그래프로 바꿔도 mst가 같게 나옴 (크루스칼 생각해보면 됨) - dc App

[Bubbler(bubbler)]

그럼 이제 x방향, y방향, z방향 비용이 드는 간선끼리 따로 생각해볼 수 있음. x좌표로 정렬했을때 x좌표가 순서대로 x1, x2, x3인 세 점이 있으면, x1과 x3을 연결하는 거보다는 당연히 x1-x2, x2-x3을 연결하는게 이득이므로, 좌표순으로 이웃한 두 점 간의 간선만 생각하면 됨 - dc App

[Bubbler(bubbler)]

이제 남아있는 간선들 중에서 서로 같은 노드 쌍을 잇는 간선들의 비용을 min 해줬을때 원래 그래프에서의 비용이 나오면 ok, 아닌 경우는 예를 들어 A와 B가 x좌표가 가장 가까운데 그 사이에 C가 있는 경우가 있는데 역시 크루스칼에서 AC와 CB가 먼저 처리될 것이므로 이런 경우는 무시해도 됨 - dc App

[익명(211.36)]

그니까 x1-x3간선은 x1-x2-x3 간선보다 효율이 좋을 수가 없기 때문에 그냥 배제해버려도 된다는 것?

[Bubbler(bubbler)]

ㅇㅇ 맞음 - dc App