데브카이브 데브카이브

서론최소 신장 트리를 구하는 알고리즘은 크루스칼 알고리즘에 대해 알아보고 관련된 백준 1197 문제를 풀어보자.최소 신장 트리에대한 설명은 아래 글을 참고하자.2024.08.13 - [알고리즘] - 최소 신장 트리 최소 신장 트리신장 트리 (Spanning Tree)신장 트리는 다음과 같은 특징을 가진다.그래프의 모든 정점을 포함한다최소한의 간선의 개수를 가진다 ( 즉, 정점의 개수 - 1 개의 간선을 가진다)트리이기에 사이클을 가devchive.tistory.com 크루스칼 알고리즘최소 신장 트리(이하 MST)를 구하는 크루스칼 알고리즘은 다음과 같은 순서를 가진다.간선의 크기를 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택한다현재 선택한 간선이 정점 U,V를 연결하는 간선이라고 할 때, 만약 U..