728x90 🥇Baekjoon Solutions/Union-Find & 크루스칼 알고리즘11 [C++] 백준 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 풀이 최소 스패닝 트리(크루스칼 알고리즘)의 가장 기본적인 문제입니다. 유니온-파인 개념을 사용하여 사이클이 발생하지 않는 방향으로 모든 연결 간선들을 분석해 줍니다. #include #include #include using namespace std; class edge { public: int node[2]; int distance; edge(in.. 2021. 8. 19. [C++] 최소 스패닝 트리(크루스칼 알고리즘) 최소 스패닝 트리란? 트리는 N개의 정점이 N-1개의 간선으로 연결되어 있으면서 어느 두 노드를 잡아도 가지 못하는 경로가 존재하지 않습니다. 일반적으로 트리를 만들 때, 가중치를 고려하지 않고 트리를 구성합니다. 간선에 가중치가 존재하기 때문에 최소 스패닝 트리가 있는 것입니다. 최소 스패닝 트리는 간선을 N-1개의 간선을 뽑아내서 트리를 구성하면서, 뽑아낸 간선의 총 합이 제일 작아야합니다. 최소 스패닝 트리의 주요 포인트 1) 우선 N개의 정점이 트리가 되어야한다. 2) 뽑은 간선의 총합이 제일 작아야한다. 구현 1) 트리를 구성하기 위해서는 union-find 알고리즘의 union을 써서 쉽게 구현이 가능합니다. 2) 다음 뽑은 간선의 총합을 제일 작게 해기 위해서는 우선 간선을 오름차순 .. 2021. 8. 8. 이전 1 2 다음 728x90
