[일반] D질문좀여

[익명(223.62)]

MST 만들어야겠단 생각은 했는데 점개수 넘마나서 못만드렀는데 대체 어케하는거애요?

[0xrgb(0xrgb)]

점개수가 아니라 엣지개수가 문제인데 잘 생각해보면 x축 정렬 했을때 양쪽에서 가장 가까운 점으로 잇는 엣지랑 y축 정렬 했을때 양쪽에서 가장 가까운 점으로 잇는 엣지만 고려하면 됩니다. 이러면 엣지의 수가 O(N) 이니까 O(N lg N)에 크루스칼 사용 가능한 각이고요

[익명(223.62)]

아 그리디하게 이어야하니까 그게 무적권 답이 되는건가요? 삼각부등식인가 그거?

[0xrgb(0xrgb)]

A B C가 있으면 A B, B C 이어지고 난 뒤에야 A C가 이어질 가능성이 생김 (AC = AB + BC 이기 때문) 그런데 이미 저기까지 왔으면 AB, BC가 연결되어 있다는 말이니까 크루스칼 알고리즘 상 AC 연결을 안함 그래서 무시해도 됩니다