개념스패닝 트리 (간선의 수 최소. 사이클이 생기면 안됨). 를 만드는 알고리즘그리디 알고리즘. 길이(가중치)가 가장 작은 간선부터 연결함. 근데 그러다 보면 사이클이 생길 수 있음.사이클을 피하는 알고리즘 필요. 방법 : 사이클 피하기간선이 연결된 노드들을 그룹으로 묶고 같은 그룹끼리 연결하는 간선은 피하는 것, Disjoint Set을 활용함. 우선 간선후보들을 가중치 순으로 정렬함간선 후보목록을 순회하며 가중치가 가장 작은 간선후보부터 사이클 검사를 함(Disjoint Set을 사용해 간선에 연결된 두 정점이 같은 팀인지 확인함). 참고 DisjointSet: https://ddukddaksudal.tistory.com/54같은 팀이면 다음 간선 후보로 넘기고 다른 팀이면 간선을 추가함(연결함). ..
