대표적인 Union-find 알고리즘과 크루스칼 알고리즘 문제다. 비슷한 문제로는 백준 1197번 최소 스패닝 트리 문제(https://www.acmicpc.net/problem/1197)가 있다. 최소 스패닝 트리 문제는 지난번에 풀어놨으니 참고하면 될 듯하다. https://yuldangs-sosolife.tistory.com/entry/%EB%B0%B1%EC%A4%80-1197%EB%B2%88-C-%EC%B5%9C%EC%86%8C-%EC%8A%A4%ED%8C%A8%EB%8B%9D-%ED%8A%B8%EB%A6%AC [백준 1197번 C++] 최소 스패닝 트리 ㅂ크루스칼 알고리즘과 Union Find 알고리즘을 연습하기 좋은 문제다. https://www.acmicpc.net/problem/1197 1..

불쌍한 준석이를 도와주기위해 풀었던 문제... Union Find 알고리즘을 활용하여 푸는 문제로, 각각의 정점을 입력 받을 때 친구비가 가장 적게 드는 정점으로 부모노드를 지정하여 합집합을 만든 후 순차적으로 정점을 탐색하며 해당 정점의 부모노드가 탐색되지 않은 부모노드일 경우 check 한 이후 cost를 더해가면 된다. 다른 사람 풀이도 참고를 했는데, 결과적으로 중요한건 합집합을 모두 완성한 후 해당 노드가 탐색하지 않은 노드일 경우(같은 집합이 아닌 경우) 해당 cost를 더해주는 것이 중요하다. 나는 check 배열을 선언해 해당 정점이 탐색하지 않은 정점일 경우 cost에 더해주었다. 혹은 탐색하지 않은 정점일 경우 cost를 더해준 이후 0으로 합집합을 만들어주는 방식도 있다. 또한 친구비..

ㅂ크루스칼 알고리즘과 Union Find 알고리즘을 연습하기 좋은 문제다. 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 크루스칼 알고리즘은 Greedy 알고리즘의 일종으로, 트리의 간선을 오름차순으로 정렬한 후 가중치가 가장 적은 간선부터 cycle이 생기기 전까지 차례로 합집합으로 만들어나가는 알고리즘이다. cycle의 생성 유무는 Union-Find 알고리즘으로 확인할 수 있다. 간선 정보를..