목록최소 스패닝 트리 (1)

hades

[Baekjoon] 1197번: 최소 스패닝 트리

🥅 문제https://www.acmicpc.net/problem/1197 🔍 설계단순히, 최소 스패닝 트리를 구현하는 문제이다.  최소 스패닝 트리를 어떻게 구현하는지 복기해보자. 1. 간선 정보를 비용을 기준으로 오름차순으로 정렬한다. 본인은 우선순위 큐를 사용하였다.2. 우선순위 큐에서 하나씩 꺼내서(= 비용이 작은 간산부터) 두 정점을 연결 시도한다. 두 정점의 부모가 같은 경우, 이미 연결되어 있다는 뜻이므로 넘어간다. 두 정점의 부모가 다른 경우, 연결되어 있지 않다는 의미이므로 union을 통해 연결하고 가중치에 비용을 추가한다. 👊 풀이#include #include #include #include using namespace std;int v, e, a, b, c, result = 0..
👊 PS/Algorithm 2024. 9. 2. 18:36
이전 Prev 1 Next 다음