728x90
- 탐욕적인(greedy) 방법과 Disjoint Set을 이용하여 MST(Minimum Spanning Tree)를 구한다.
구현 방법 Steps
1. 최소 코스트 경로를 임의로 선택
2. DisjointSet을 이용하여 해당 경로가 사이클이 발생 했는지 체크
3. 다음 최소 코스트 경로를 기준으로 step 반복
제시된 상황
1. 최소 경로 중 임의 경로 선택
2. 선택된 경로 중 싸이클이 발생 했는지 확인
3. DisjointSet을 이용하여 경로 채택 여부 판단
Result
728x90
'Algorithm > Concepts' 카테고리의 다른 글
| DynamicProgramming,동적계획법,DP (0) | 2021.08.22 |
|---|---|
| 프림,RPIM MST (0) | 2021.08.22 |
| 정렬,버블,선택,삽입,힙,병합,퀵,Sort,Bubble,Selection,Insert,Heap,Merge,Quick (0) | 2021.08.21 |
| 이진탐색,이진탐색트리,BinarySearch,BinarySearchTree (0) | 2021.08.19 |
| 길찾기,에이스타,PathFinding,AStar,A* (0) | 2021.08.19 |