이번 포스트에서는 MST를 구하기 위한 Kruskal 알고리즘에 대해 살펴보자. Kruskal 알고리즘 알고리즘 개요크루스칼 알고리즘은 간선을 중심으로 MST를 구하는 알고리즘이다. 어차피 MST는 트리이므로 Circle을 만들지 않으면서 비용이 작은 간선들을 계속해서 연결하다보면 MST가 구성되는 특징을 이용한다.Kruskal의 기본 동작은 다음과 같다.모든 간선을 가중치에 따라 오름차순으로 정렬한다.간선을 하나씩 연결해간다. - 이 과정에서 Circle이 발생하면 그 간선은 버리고 다음 간선을 선택한다.트리이므로 N-1개의 간선이 선택되면 종료한다. 알고리즘 전개 절차  기본 코드Kruskal은 최소 비용의 간선들을 연결하는 과정에서 Circle을 판별하기 위해 Union-Find 자료구조를 사용한다..

BJ G3 17472 다리 만들기 2 문제링크 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://www.youtube.com/watch?v=Vop0L7vU1-0 소스 보기 동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다...