1774번: 우주신과의 교감 문제 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 풀이 모든 우주신들 간 최단 통로로 연결이 되어있어야 하므로 최소 스패닝 트리(MST)를 구하면 된다. 모든 우주신의 좌표를 입력받은 후 서로 간의 거리를 모두 구해 간선으로 추가한다. 이후 이미 연결된 통로인 경우에는 미리 두 점을 union 시켜 MST에서 제외시켜 주고 크루스칼 알고리즘을 사용해 MST를 구한다. 이때 구해지는 가중..