Stargazer

접근: 이름 부터 최소 스패닝 트리를 구하는 문제 이에 대한 알고리즘은 prim 알고리즘과 kruskal 알고리즘이 유명하다 전략: prim보다는 krusal이 조금 더 접근하기 쉬울 것 같아서 선택했으나, 둘 중 뭘 선택 해도 상관은 없다. 간선을 가중치가 낮은 순서대로 정렬을 한 후에, 작은 것부터 하나씩 tree에 추가한다. 추가할 때는 사이클이 발생하지 않도록 해야하기 때문에, 간선을 추가하려고 할때 두 정점이 같은 집합인지를 확인한다. 같은 집합이라면 패스하고 다음 간선을 조사한다. n-1번이 추가되면 종료한다. (다만 다음 코드 상에는 딱히 최적화를 진행하지 않고, 전체 조사를 하도록 하였다.) 구현: #include #include #include using namespace std; str..