문제를 요약하면..
최소 신장 트리 (=최소 스패닝 트리 = Minimum Spanning Tree)
중에서 사용된 간선들의 가중치 합이 최소인 트리를 찾아
간선의 가중치 합 최솟값 찾기!
해결하기 위해서는 "크루스칼 알고리즘" 사용
-
최소 비용 신장 트리 찾는 알고리즘
-
가장 적은 비용으로 모든 노드를 연결 (노드 수 : N, 간선 : N-1개)
※용어정리※
스패닝 트리 : 그래프에서 일부 간선을 선택해서 만든 트리
최소 스패닝 트리 : 스패닝 트리 중에 선택한 간선의 가중치의 합이 최소인 트리
시도1. 크루스칼 알고리즘 사용 (정답)
-
모든 간선의 가중치를 오름차순으로 정렬
-
가중치가 가장 작은 edge 선택
-
이전에 노드와 같은 집합이 아니라면, 즉, 연결되어 있지 않다면 2개의 노드를 서로 연결한다.
(만약 연결되어 있는 상태에서 연결해준다면 사이클이 발생하므로 오류!)
과정 정리
1- find_parent 함수는 해당 노드의 "root node"를 반환하는 함수이다
"이 함수는 언제 사용하는가?"두 노드를 연결하기 전 프루스칼 알고리즘은 두 노드가 같은 집합인지, 즉, 연결되어있는지 항상 검사해야한다.
그렇기 위해서 두 노드의 root node를 찾아 비교해야 된다.
두 노드의 root node 가 같다 --> 이미 연결되어 있다. (사이클이 발생하므로 연결 불가능!)
두 노드의 root node 가 다르다 --> 연결되어 있지 않으므로 연결 가능하다.
2- union_parent 함수는 두 노드를 연결해주는 함수이다.
"어떻게 연결해주느냐?"
함수 호출 전 parent 리스트가 있다.
parent 리스트는 각 노드의 부모노드를 저장하는 리스트로, 초기에는 자기자신을 부모노드로 설정해놓는다.
이 의미는 모든 노드의 root node가 연결되어 있지 않은 서로소 집합임을 나타내기 위함이다.
그럼 이제 union_parent를 이용해 두 노드를 연결해주는데, 이때 두 노드의 값이 작은 것을 부모로 저장한다. ( 이 조건은 내 마음대로 해도 된다.. 결과에는 영향 없음)
3- 크루스칼 알고리즘을 사용하기 위해 edge 비용을 오름차순 정렬해야한다.
크루스칼을 정렬 부분에서 오래 걸리 수 있다. 그렇기 때문에 최적화된 내장된 함수 sort()를 이용해 O(NlongN) 발생
4- 최소 edge부터 시작하여 노드를 연결해간다. (단, 사이클을 방지하기 위해 노드 연결유무를 항상 if문으로 check하며 연결한다.)
※참고 사이트※
이론 내용 참고
https://velog.io/@fldfls/%EC%B5%9C%EC%86%8C-%EC%8B%A0%EC%9E%A5-%ED%8A%B8%EB%A6%AC-MST-%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%B9%BC-%ED%94%84%EB%A6%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
이론 및 코드 참고
https://www.youtube.com/watch?v=aOhhNFTIeFI
