밀래의 코딩북

백준 알고리즘 문제 1922 문제를 정리하는 포스팅입니다. 최적의 코드가 아니니 해당 코드는 참고만 하시기 바랍니다. 1. 최소신장트리 ( Minimum Spanning Tree ) 이 문제는 최소 신장 트리 문제입니다. 최소 신장 트리(MST)는 그래프 알고리즘 중 하나 입니다. 최소 신장 트리(MST)는 Kruskal 알고리즘과 Prim 알고리즘이 있습니다. 이 문제는 Kruskal 알고리즘 문제로 다음과 같이 생각해볼 수 있습니다. 그래프의 간선들을 가중치의 오름차순으로 정렬한다. 정렬된 간선 리스트에서 순서대로 사이클이 생기지 않는 간선을 선택합니다. - 비용이 낮은 순서로 간선을 선택합니다. - 사이클이 생성되지 않는다 함은 노드-1개의 간선을 선택한다는 의미 입니다. 선택된 간선을 현재 MST..