Algorithm & Data Structure
[백준] 다리 만들기 2 (17472번) - Python / MST ( Kruskal Algorithm )
✅ 문제 - [백준] 다리 만들기 2 (17472번) ✅ 필요 알고리즘 개념 - BFS / MST ( Kruskal Alogorithm )🎯 크루스칼 알고리즘( Kruskal Alghrithm ) 이란?크루스칼 알고리즘이란, 그래프 자료구조에서 그리디 알고리즘을 적용해 MST ( Minimum Spanning Tree , 최소 신장 트리 )를 찾는 방법이다. 그리디 알고리즘의 경우 순간의 최선의 선택이 결과적으로 최선의 선택임을 증명해야 하는데MST를 푸는 알고리즘 중 프림(Prim's) 알고리즘과 크루스칼(Kruskal) 알고리즘은 그리디 알고리즘이므로 해결 가능함이 이미 증명이 된 알고리즘이다. 크루스칼 알고리즘을 적용하는 순서는 다음과 같다.간선을 리스트에 ( 길이, 노드1, 노드2 ) 형식으..
