728x90
문제풀이
최소 스패닝 트리(Minimum Spanning Tree)
정점과 정점을 연결하는 간선의 가중치가 동일하지 않을 때 가중치가 작은 간선을 골라 연결한다고해서 최소 스패닝 트리라고 한다.
간선이 작은 순서대로 연결하고 싸이클이 생기지 않도록 연결하는 방법이다.
N개의 정점을 연결하는 간선의 개수는 반드시 N-1 개이다.
최소 스패닝 트리를 만드는 대표적인 알고리즘으로 Kruskal, Prim 이 있는데 오늘은 크루스칼 알고리즘을
이용해 해결해 보았다.
구현 알고리즘
1. Kruskal 알고리즘
- 그리디한 방법을 이용한다.
- 간선의 가중치를 오름차순으로 정렬하고
- 정렬된 간선 리스트를 순서대로 탐색하면서 싸이클이 생겼는지 확인한다.
다음 유튜브를 보면 자세하게 나와있으니 한번 보면 내 설명보다 훨씬 이해가 잘된다.
https://www.youtube.com/watch?v=LQ3JHknGy8c&t=462s
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
import java.util.*;
import java.io.*;
class Main{
static int n,m;
static int[] parent;
static PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>(){
public int compare(Edge a, Edge b)
{
if(a.dist < b.dist) return -1;
else if(a.dist > b.dist) return 1;
else return 0;
}
});
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
parent = new int[n+1];
for(int i=1;i<=n;i++)
{
parent[i] = i;
}
for(int i=0;i<m;i++)
{
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
pq.add(new Edge(a,b,c));
}
int sum = 0;
for(int i=0;i<m;i++)
{
Edge e = pq.poll();
if(find(e.node1) != find(e.node2))
{
sum += e.dist;
union(e.node1, e.node2);
}
}
System.out.println(sum);
}
static int find(int x)
{
if(parent[x] == x) return x;
else return parent[x] = find(parent[x]);
}
static void union(int x, int y)
{
x = find(x);
y = find(y);
if(y>x)
parent[y] = x;
else
parent[x] = y;
}
}
class Edge{
int node1;
int node2;
int dist;
public Edge(int node1, int node2, int dist)
{
this.node1 = node1;
this.node2 = node2;
this.dist = dist;
}
}
|
cs |
https://www.acmicpc.net/problem/1197
1197번: 최소 스패닝 트리
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이
www.acmicpc.net
LIST
'Programming > Algorithm' 카테고리의 다른 글
| [Sort] BOJ 1181번, 단어 정렬(JAVA) (2) | 2021.10.31 |
|---|---|
| [Topology Sort] BOJ 2252번, 줄 세우기(JAVA) (0) | 2021.10.29 |
| [BFS] BOJ 2583번, 영역 구하기(JAVA) (0) | 2021.10.28 |
| [BFS] BOJ 7562번, 나이트의 이동(JAVA) (0) | 2021.10.28 |
| [BFS] BOJ 7569번, 토마토(JAVA) (0) | 2021.10.28 |