크루스칼

[JAVA] 백준 1774번 : 우주신과의 교감

문제 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 해결 방법 크루스칼 알고리즘을 활용해서 풀었다. 크루스칼이란 간단하게만 설명하면, 정점들과 이어진 간선의 거리를 기준으로 정렬한 뒤에 정렬된 순서대로 접근하여 유니온-파인드를 활용하여 앞의 두 정점이 연결되어 있지 않으면 연결시켜주는 방식으로써 가장 짧은 거리의 간선이 제일 앞으로 정렬되어 있기 때문에 제일 짧은 경로를 만들어 낼 수 있다. 문제에서 이미 연결된 통로로 주어지는 값들은 거리를 0으로 설정해서 리스트에 입력해주는 방..