최소 스패닝 트리

[백준] 10423. 전기가 부족해 (Java)

문제 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 알고리즘 그래프 이론, 최소 스패닝 트리, 크루스칼 알고리즘 풀이 모든 도시에 전기를 공급하기 위한 케이블 연결의 최소 비용을 구하는, 즉 모든 정점을 잇는 간선의 최소 비용을 구하는 최소 스패닝 트리 문제로 크루스칼 알고리즘을 사용하여 해결하였다. 이미 발전소가 지어져있고, 한 도시는 하나의 발전소에서만 전기를 공급 받아야하므로 두 도시를 연결할 때, 두 도시의 루트 노드가 발전소라면 두 발전소에서 전기를 공급받게..

[백준] 16398. 행성 연결 (Java)

문제 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 알고리즘 그래프, 최소 스패닝 트리, 크루스칼 알고리즘 풀이 제국 내 모든 행성을 연결하고, 유지 비용을 최소화해야하므로, 크루스칼 알고리즘을 사용하여 모든 행성을 연결하는 최소 유지 비용을 구한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.S..

[백준] 1774. 우주신과의 교감 (Java)

문제 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 알고리즘 그래프, 최소 스패닝 트리, 크루스칼 알고리즘 풀이 우주신들이 바로 황선자씨와 연결될 필요없이 우주신들을 거쳐서 교감을 하면 되기 때문에 각 우주신들을 모두 연결하는 최소 통로 길이를 구하면 된다. 따라서 최소 스패닝 트리를 만드는 문제이므로 크루스칼 알고리즘을 사용한다. 각 우주신들의 위치가 2차원 좌표로 주어져있으므로 우주신들 사이의 거리를 구해 이를 가중치로 우선순위 큐에 저장하여 크루스칼 알고리즘을 진행한다. 코드..

[백준] 1368. 물대기 (Java)

문제 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 알고리즘 그래프, 최소 스패닝 트리 풀이 최소 하나의 논, 혹은 여러 논에 우물을 파고, 이를 이용해서 모든 논을 이어야하는 최소 스패닝 트리 문제이다. 따라서 우물을 파는 것을 다른 하나의 논(0번 논)에서 물을 끌어오는 것으로 생각하면 단순한 최소 스패닝 트리 문제가 된다. 다음은 예제 입력 1 그래프와 0번 논을 추가한 그래프이다. 따라서 우물을 파는 비용을 0번 노드와 i번 노드의 가중치로 만들고, 크루스칼 알고리즘을 ..

[백준] 17472. 다리 만들기 2 (Java)

문제 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 알고리즘 구현, 그래프, 브루트포스, 너비우선탐색(BFS), 최소 스패닝 트리(MST), 크루스칼 알고리즘(Kruskal) 풀이 모든 섬을 연결해야하므로 최소 스패닝 트리를 사용한다. 각 섬을 노드로, 이을 수 있는 다리를 간선으로 하여 그래프를 만든 후, 크루스칼 알고리즘을 이용하여 그래프를 이을 수 있는 최솟값을 구한다. 1. 섬에 2부터 N+2의 번호를 부여한다. 2. 너비우선탐색(BFS)를 이용하여 각 섬을 잇는 다리(간선)를 모..

[백준] 1197. 최소 스패닝 트리 (Java)

🔒 문제 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 🔑 알고리즘 최소 스패닝 트리(MST), 크루스칼 알고리즘(Kruskal) 💡 풀이 최소 스패닝 트리를 찾는 알고리즘으로 크루스칼과 프림 알고리즘이 유명하다. 크루스칼 알고리즘은 그리디하게 가장 가중치가 낮은 간선들부터 연결하는 방법으로 간선을 정렬해야하기 때문에 O(ElogE)의 시간 복잡도를 갖는다. 해당 문제는 간선 10,000, 정점이 100,000인 희소그래프이기 때문에 O(V2) 의 시간 복잡도를..