https://programmers.co.kr/learn/courses/30/lessons/62050
- flow
- 가장 먼저 너비 우선 탐색(bfs)를 이용해 region growing 하듯이 사다리가 필요없는 그룹끼리 같은 노드로 묶는 작업이 필요하다. (dfs도 상관 없음)
- 이후 그룹을 노드라고 생각하고 그래프를 만든다 생각해보면, 높이차가 간선(edge) 가중치이고, 이에 따라 수많은 간선들이 나타나게 되는데 2개의 노드 사이에는 가장 작은 값인 edge 를 제외하고 고려하지 않아도 되므로 그래프 간소화 작업이 필요하다.
- 그렇게 만든 그래프를 가지고 minimum spanning tree(mst)를 만들어 비용합을 구하면 답이 된다. 이 때 쓰이는 알고리즘은 흔히 prim 또는 kruskal이 있다. (모두 greedy한 방법)
필자는 예전 문제때 짰던 kruskal 을 그대로 이용했는데 성능 개선을 위해선 더 세심한 코딩이 필요하다. 시간복잡도가 O(N^2) 이라 그런지 몇가지 케이스에 대해 시간 초과가 나온다. 시간복잡도를 개선할 방법이 떠오르지 않아 단순 코드 최적화는 일단 넘어가기로 했다.
