목록MST (1)

ULISIA's Developer Life

[Backjoon] 1197 최소 스패닝 트리 Python 문제 풀이

출처:1197번 최소 스패닝 트리 문제해석 최소 신장 트리 (minimum spanning tree) 전체 요소들을 연결할때 사용한다. Kruskal 알고리즘, Prim 알고리즘이 있다. Kruskal 간선들을 정렬 간선이 잇는 두 정점의 root를 찾는다. 다르다면 하나의 root를 바꾸어 연결 시켜준다. Prim 임의의 정점을 선택 해당 정점에서 갈 수 있는 간선을 minheap(최소힙)에 넣는다. 최소값을 뽑아 해당 정점을 방문하지 않았다면 선택한다. Kruskal 알고리즘은 간선들을 정렬해야하기 때문에 간선이 적다면 Kruskal, 많다면 Prim을 선택한다. 비슷한 알고리즘으로 다익스트라 알고리즘이 있다. 다익스트라는 전체 요소를 연결하는 것이 아닌 한 정점에서 다른 정점으로 가는 가장 짧은 방..
Algorithm/Backjoon 2023. 7. 18. 16:45
이전 Prev 1 Next 다음