이 문제는 최소 스패닝 트리를 구현하는 방법중 크루스칼 알고리즘을 이용하여 구현하면 된다.
크루스칼 알고리즘은 그래프 사이 연결의 최소비용을 찾으면 된다.
간선을 비용순으로 정렬하고,
가장작은 비용이 들어가는 간선을 사이클이 생기지 않는 순서대로 선택하면된다.
간선 사이의 사이클은 union, find 연산을 이용하여 처리한다.
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준][DP] 11060 점프점프 (0) | 2017.08.23 |
---|---|
[백준] 1005 ACM Craft (0) | 2017.07.20 |
[백준] 1717 집합의 표현(유니온 파인드) (0) | 2017.07.06 |
[백준][그래프] 2623 음악프로그램 (0) | 2017.07.04 |
[백준][위상정렬] 2056 작업 DAG (0) | 2017.06.27 |