[백준 1647번 c++ 풀이] - 도시 분할 계획

걸린시간: 3시간 mst문제인건 처음에 바로 파악했으나, mst를 짜본적이 없어 시간이 오래 걸렸다. 가장 시간을 많이 잡아먹었던 이유는 내가 크루스칼 mst를 사용하여 풀었는데, 크루스칼 mst의 특성상 아무리 정렬을 한다고 하더라도 간선이 많을경우 시간이 매우 오래 걸린다. 그래서 union-find를 사용해주어야 하는데, 유니온 파인드를 사용하더라도 시간이 오래걸리는 경우가 있다. 그 이유는 트리구조가 편향적으로 생성이 될경우 각 트리의 중심노드를 참조하면서 최종 중심노드를 찾아가는 방식으로 중복검사를 하게 되는데, 임의적으로 노드를 균형있게 제시하지 않게 되면 시간이 오래걸려 큰 시간차가 발생한다. #include #include #include #include using namespace std..

원문링크 : [백준 1647번 c++ 풀이] - 도시 분할 계획