목록프림알고리즘 (1)

코딩성장스토리

백준 1197번: 최소 스패닝 트리(프림 알고리즘)

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 이 문제는 최소신장 트리 이다. 최소 신장 트리는 크루스칼 알고리즘과 프림 알고리즘으로 풀 수 있는데 나는 BFS에 우선순위 큐만 더하면 된다고 생각해서 프림 알고리즘으로 풀었다. 프림 알고리즘은 간단하게 시작 노드에서 가중치가 작은 간선을 이어가며 구하는 것이다. 크루스칼 알고리즘은 사이클이 생성되지 않게 작은 가중치를 가진 간선을 연결하는 것이다...
백준 코딩 2022. 8. 21. 00:22
이전 Prev 1 Next 다음