BOJ 18976

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

 

 

코드

http://boj.kr/97c257d8f1b74482be14bb8980f3227c

 

Petrozavodsk Programming Camp Summer 2018 Day 3: MIPT Contest K

 

난이도 : P2

 

Elapse Time : 15min

 

문제를 보고 단순화를 해야겠다는 생각이 들었다. 결국 문제를 요약하면 점과 선분들에 의해 몇 개로 나누어져 있는 평면에서 최소비용의 선분을 제거하여 평면이 분리되어 있지 않도록 만들라는 것이었다. 처음에는 분리되어 있는 평면들에 각각 번호를 붙여준 뒤 비용 순으로 선분들을 정렬하고 선분을 기준으로 양쪽에 있는 평면이 같은 평면인지 확인하는 것을 Dsu를 활용해 처리해 줄 생각이었다. 평면이 어떻게 나누어져 있는지 확인할 때 어떻게 할 것인지 생각하다가 선분을 추가해갈 때 연결하려는 두 점이 이미 연결되어 있으면 평면이 나누어진다는 것을 알게 되었다. 이로부터 더 쉬운 풀이를 도출해 냈는데 선분들을 비용 내림차순으로 정렬해 두고 선분이 연결할 두 점이 이미 연결되어 있으면 이 선분은 추가할 수 없으므로 제거해야 하는 선분이 된다. 선분이 이미 연결되어 있는지는 Dsu로 판단해 주고 선분이 비용 내림차순으로 정렬되어 있기 때문에 이를 통해 구한 답이 최소가 됨이 보장된다.