๋ํ์ด๋ ์ปดํจํฐ์ ์ปดํจํฐ๋ฅผ ๋ชจ๋ ์ฐ๊ฒฐํ๋ ๋คํธ์ํฌ๋ฅผ ๊ตฌ์ถํ๋ ค ํ๋ค. ํ์ง๋ง ์์ฝ๊ฒ๋ ํ๋ธ๊ฐ ์์ง ์์ ์ปดํจํฐ์ ์ปดํจํฐ๋ฅผ ์ง์ ์ฐ๊ฒฐํ์ฌ์ผ ํ๋ค. ๊ทธ๋ฐ๋ฐ ๋ชจ๋๊ฐ ์๋ฃ๋ฅผ ๊ณต์ ํ๊ธฐ ์ํด์๋ ๋ชจ๋ ์ปดํจํฐ๊ฐ ์ฐ๊ฒฐ์ด ๋์ด ์์ด์ผ ํ๋ค. (a์ b๊ฐ ์ฐ๊ฒฐ์ด ๋์ด ์๋ค๋ ๋ง์ a์์ b๋ก์ ๊ฒฝ๋ก๊ฐ ์กด์ฌํ๋ค๋ ๊ฒ์ ์๋ฏธํ๋ค. a์์ b๋ฅผ ์ฐ๊ฒฐํ๋ ์ ์ด ์๊ณ , b์ c๋ฅผ ์ฐ๊ฒฐํ๋ ์ ์ด ์์ผ๋ฉด a์ c๋ ์ฐ๊ฒฐ์ด ๋์ด ์๋ค.)
๊ทธ๋ฐ๋ฐ ์ด์์ด๋ฉด ์ปดํจํฐ๋ฅผ ์ฐ๊ฒฐํ๋ ๋น์ฉ์ ์ต์๋ก ํ์ฌ์ผ ์ปดํจํฐ๋ฅผ ์ฐ๊ฒฐํ๋ ๋น์ฉ ์ธ์ ๋ค๋ฅธ ๊ณณ์ ๋์ ๋ ์ธ ์ ์์ ๊ฒ์ด๋ค. ์ด์ ๊ฐ ์ปดํจํฐ๋ฅผ ์ฐ๊ฒฐํ๋๋ฐ ํ์ํ ๋น์ฉ์ด ์ฃผ์ด์ก์ ๋ ๋ชจ๋ ์ปดํจํฐ๋ฅผ ์ฐ๊ฒฐํ๋๋ฐ ํ์ํ ์ต์๋น์ฉ์ ์ถ๋ ฅํ๋ผ. ๋ชจ๋ ์ปดํจํฐ๋ฅผ ์ฐ๊ฒฐํ ์ ์๋ ๊ฒฝ์ฐ๋ ์๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์ปดํจํฐ์ ์ N (1 โค N โค 1000)๊ฐ ์ฃผ์ด์ง๋ค.
๋์งธ ์ค์๋ ์ฐ๊ฒฐํ ์ ์๋ ์ ์ ์ M (1 โค M โค 100,000)๊ฐ ์ฃผ์ด์ง๋ค.
์ ์งธ ์ค๋ถํฐ M+2๋ฒ์งธ ์ค๊น์ง ์ด M๊ฐ์ ์ค์ ๊ฐ ์ปดํจํฐ๋ฅผ ์ฐ๊ฒฐํ๋๋ฐ ๋๋ ๋น์ฉ์ด ์ฃผ์ด์ง๋ค. ์ด ๋น์ฉ์ ์ ๋ณด๋ ์ธ ๊ฐ์ ์ ์๋ก ์ฃผ์ด์ง๋๋ฐ, ๋ง์ฝ์ a b c ๊ฐ ์ฃผ์ด์ ธ ์๋ค๊ณ ํ๋ฉด a์ปดํจํฐ์ b์ปดํจํฐ๋ฅผ ์ฐ๊ฒฐํ๋๋ฐ ๋น์ฉ์ด c (1 โค c โค 10,000) ๋งํผ ๋ ๋ค๋ ๊ฒ์ ์๋ฏธํ๋ค. a์ b๋ ๊ฐ์ ์๋ ์๋ค.
์ถ๋ ฅ
๋ชจ๋ ์ปดํจํฐ๋ฅผ ์ฐ๊ฒฐํ๋๋ฐ ํ์ํ ์ต์๋น์ฉ์ ์ฒซ์งธ ์ค์ ์ถ๋ ฅํ๋ค.
๐ก Kruskal Algorithm ์ด์ฉ โ MST ๋ฌธ์
๐ก ์์์ ๊ณผ ๋์ ์ด ๊ฐ์ ์ ์๋ค๋ ์กฐ๊ฑด์ด ์ถ๊ฐ๋ MST ๋ฌธ์
1) ์์์ ๊ณผ ๋์ ์ด ๊ฐ์ผ๋ฉด ์ฌ์ดํด์ด๋ ์์ ์ ์ฅํ์ง ์์
for(int i=0; i<m; i++) {
String[] s = br.readLine().split(" ");
int start = Integer.parseInt(s[0]);
int end = Integer.parseInt(s[1]);
int cost = Integer.parseInt(s[2]);
if(start == end)
continue;
pq.add(new Edge(start, end, cost));
}
์ดํ MST ๊ตฌํ๋ ๋ฐฉ์๊ณผ ์ฝ๋ ๊ฐ์
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.io.IOException;
public class Graph_8 {
static int[] parent;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
parent = new int[n+1];
for(int i=1; i<n+1; i++)
parent[i] = i;
PriorityQueue<Edge> pq = new PriorityQueue<>();
for(int i=0; i<m; i++) {
String[] s = br.readLine().split(" ");
int start = Integer.parseInt(s[0]);
int end = Integer.parseInt(s[1]);
int cost = Integer.parseInt(s[2]);
if(start == end)
continue;
pq.add(new Edge(start, end, cost));
}
int ret = 0;
while(!pq.isEmpty()) {
Edge e = pq.poll();
if(find(e.start) == find(e.end))
continue;
else {
union(e.start, e.end);
ret += e.cost;
}
}
System.out.println(ret);
}
static int find(int e) {
if(parent[e] == e) return e;
return parent[e] = find(parent[e]);
}
static void union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if(rootA != rootB) parent[rootB] = rootA;
}
static class Edge implements Comparable<Edge>{
int start;
int end;
int cost;
Edge(int start, int end, int cost) {
this.start = start;
this.end = end;
this.cost = cost;
}
@Override
public int compareTo(Edge o) {
return this.cost - o.cost;
}
}
}
์ฑ๊ณตโจ