백준1197 (1) 썸네일형 리스트형 최소 신장 트리 (MST) - 크루스칼/프림 알고리즘 (ft.백준 1197) 트리인데 모든 정점이 사이클없이 연결된 트리!실생활에서는,여러 도시를 도로, 전력선, 수도관 등으로 연결할 때, 건설 비용이나 유지비를 최소화하는 경로를 찾는 데 활용된다고 한다.꽤나 유용한 알고리즘이다. 보통 아래 두가지 알고리즘을 사용한다. Kruskal 크루스칼 알고리즘 (간선이 적을 때)Prim 프림 알고리즘 (간선이 많을 때) 적다, 많다 기준을 정하기가 애매하긴 한데 두가지 방법으로 모두 백준 풀어보았다. • 다음 간선 선택 기준의 범위: • 크루스칼: 전체 간선 중에서 최소 간선을 선택 (전역적으로 선택) • 프림: 현재 MST와 연결된 간선 중에서 최소 간선을 선택 (동적으로 확장) • 알고리즘의 흐름: • 크루스칼: 간선을 하나씩 추가하면서 사이클 없이 트리를 .. 이전 1 다음
