크루스칼
-
[백준]2887: 행성 터널 - JAVA문제풀이/백준 2021. 2. 16. 18:57
[백준]2887: 행성 터널 www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 MST유형의 문제로, 모든 간선의 정보를 만들어서 그 중에 작은 간선을 선택하면서 최소 간선을 찾을 수 있게 kruskal 알고리즘을 사용하여 구현하였다. 행성의 정보를 입력받을때 이차원배열을 사용하여 2중 반복문으로 모든 노드의 거리의 최솟값을 구해 q에 넣어주었더니 메모리 초과가 났다. 행성의 정보를 저장하는 class를 따로 구현해주었고 x..
-
알고리즘 - MSTCS/알고리즘 2021. 2. 15. 22:21
MST MST Minimum Spanning Trees. 최소 신장 트리. 조건: 싸이클이 없는 무향 연결 그래프. 연결 그래프란 모든 정점 간에 경로가 존재하는 그래프를 말한다. 간선의 합이 최소인 신장트리를 말한다. Prim Algorithmn 임의의 시작 노드를 골라 min heap에 insert한 후 노드와 연결된 노드를 min heap에 insert해준다. 거리가 작은 노드부터 꺼내며 꺼낼 때마다 연결된 노드를 찾아 min heap에 넣어주는 과정을 반복한다. min heap에 저장되는 정보는 현재 노드 정보와 이전 노드에서 현재 노드까지의 거리 정보이다. 수행시간: O(ElogV) 구현 with JAVA (백준 1197 최소 스패닝 트리) 1 2 3 4 5 6 7 8 9 10 11 12 13 ..