MST1 [프로그래머스] 섬 연결하기 / 파이썬 / Python / 크루스칼(Kruskal) 알고리즘 💡solutions ) 💬 '최소 비용으로 모든 노드(섬) 연결' -> 최소 신장 트리(MST)를 사용하는 크루스칼 알고리즘 활용 문제다. 신장 트리(Spanning Tree)란? 그래프 내의 모든 정점을 연결하는 트리로 간선의 개수가 n-1개로 최소 연결 부분 그래프이다. 최소 신장 트리(Minimum Spanning Tree )란? 신장 트리에서 사용된 간선들의 가중치의 합이 최소인 트리 즉, 최소 비용으로 모든 노드 연결하는 그래프이다. 참고 블로그 💬 먼저 다리 건설 비용 기준으로 costs를 오름차순 정렬한다. -> 적은 비용의 노드부터 꺼내와서 연결한다. 💬 노드의 부모를 찾는 find_parent를 통해 꺼내온 두 노드의 부모를 비교한다. ->사이클이 생기지 않게 하기 위해 부모가 다른 경우.. 2021. 11. 9. 이전 1 다음
