크루스칼3 [Java] BOJ 2887번 행성 터널 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 크루스칼 알고리즘을 이용해서 해결했습니다. 시간초과를 해결하기위해 우선 x축, y축, z축 각각 정렬을 시켜 간선리스트를 구한 후에 그 간선 리스트를 정렬하게 했습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arr.. 2021. 5. 21. [Java] Kruskal 알고리즘 MST를 찾는 알고리즘입니다. (설명을 잘 못해서 코드를 보시는 게 빠를 수 있습니다.... ㅠ) 1. 간선의 정보가 E개가 들어온다면 E개의 시작점, 도착점, 가중치를 저장할 수 있는 Edge 객체 배열을 만들고 저장하였습니다. 다음으로, 크루스칼 알고리즘은 그리디 알고리즘을 적용하고 있기 때문에 가중치를 기준으로 Edge 배열을 정렬하여 가장 낮은 가중치를 갖고 있는 간선의 정보를 우선적으로 처리하게 했습니다. 2. make() 함수를 이용해서 자기 자신이 부모가 되게 parents 배열을 초기화하는 작업을 하였습니다. 3. Edge 배열에 든 Edge들을 하나씩 처리하면서 union()을 처리하게 했습니다. union()은 최상위 부모 정점을 찾아주는 findSet을 통해 aRoot와 bRoot를 .. 2021. 4. 28. [Java] SWEA 7465번 창용 마을 무리의 개수 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 크루스칼 알고리즘을 사용하여 해결했습니다. 주의할 점은 union만 진행할 경우 최상위 그룹에 속한 부모 값만 바뀌게 되고 하위 그룹에 속한 부모 값은 바뀌지 않게 되므로 findSet을 모든 정점에서 한 번 더 진행하여 하위 그룹의 부모 값도 바뀌게 해주어야 합니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util... 2021. 4. 26. 이전 1 다음