MST

1. 개요 안녕하세요. 오늘 문제의 유형은 Minimum Spanning Tree, MST(최소 신장 트리)입니다.  N개의 별을 선으로 직/간접적으로 연결해야 합니다. 정점을 별, 별을 잇는 선을 간선이라고 한다면 별자리는 트리 구조임을 알 수 있어요! 그런데 선을 연결하는데 비용이 드네요? 이 비용을 최소화하여 연결하고 싶다고 하였으니 가중치 무방향 연결 그래프에서 최소 신장 트리를 구해야 한다는 사실을 알 수 있습니다.  간선의 가중치 정보가 실수형입니다. 부동소수점 연산은 연산을 거듭할수록 오차범위가 커지게 되므로 연산 작업을 최소화해서 푸는 것이 좋습니다. 하지만 이번 문제는 입력부터 실수로 주어져 이를 적용하기 어려운데요. 저는 가중치를 sqrt하지 않은 제곱 형태로 저장해서 풀이했습니다. 의..

1. 문제 풀이 크루스칼 알고리즘을 사용하여 풀이하였다. 랜선의 길이가 짧은 것을 우선 선택하면서 MST를 만들고, 선택되지 않은 랜선들의 길이를 모두 합하면 됩니다. 이때, Union에 성공한 간선의 개수를 세는 cnt변수를 두고 마지막에 cnt가 n-1인지 조사하면 모든 컴퓨터의 연결 여부를 확인할 수 있다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; typedef ..