๋ฌธ์
๋ํ์ด๋ ์ปดํจํฐ์ ์ปดํจํฐ๋ฅผ ๋ชจ๋ ์ฐ๊ฒฐํ๋ ๋คํธ์ํฌ๋ฅผ ๊ตฌ์ถํ๋ ค ํ๋ค. ํ์ง๋ง ์์ฝ๊ฒ๋ ํ๋ธ๊ฐ ์์ง ์์ ์ปดํจํฐ์ ์ปดํจํฐ๋ฅผ ์ง์ ์ฐ๊ฒฐํ์ฌ์ผ ํ๋ค. ๊ทธ๋ฐ๋ฐ ๋ชจ๋๊ฐ ์๋ฃ๋ฅผ ๊ณต์ ํ๊ธฐ ์ํด์๋ ๋ชจ๋ ์ปดํจํฐ๊ฐ ์ฐ๊ฒฐ์ด ๋์ด ์์ด์ผ ํ๋ค. (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๋ ๊ฐ์ ์๋ ์๋ค.
์ถ๋ ฅ
๋ชจ๋ ์ปดํจํฐ๋ฅผ ์ฐ๊ฒฐํ๋๋ฐ ํ์ํ ์ต์๋น์ฉ์ ์ฒซ์งธ ์ค์ ์ถ๋ ฅํ๋ค.
ํ์ด
์ต์ ํจ๋ํธ๋ฆฌ(ํฌ๋ฃจ์ค์นผ)๋ฅผ ์ด์ฉํ๋ ๋ฌธ์ ์๋๋ฐ์, ๊ทธ ์ด์ ๋ ๋ชจ๋ ๋คํธ์ํฌ๊ฐ ์ฐ๊ฒฐ๋๊ธฐ ๋๋ฌธ์ ํด๋น ๋คํธ์ํฌ์ ๋ฃจํธ๋ฅผ ์ฐพ์ ์ ์๊ธฐ ๋๋ฌธ์ ๋๋ค. ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ ๊ทธ๋ํ ์์์ ๊ฐ์ค์น๋ฅผ ๊ฐ์ง๋ ๊ฐ์ ์ ์ฐ๊ฒฐ ๋น์ฉ์ ์ต์๋ก ๊ฐ์ง๋ ๋ต์ ๊ตฌํ ๋ ์ฌ์ฉ๋๋๋ฐ์, ์ ๋์จ ํ์ธ๋๋ฅผ ํตํด ๋ต์ ์ฐพ์ ์ ์์ต๋๋ค. ์ฐ์ ๋ ธ๋๋ฅผ ์ ๋ ฌํ๊ธฐ ์ํด Comparable์ ๊ตฌํ ์์ํ๋๋ฐ์, ์ด๋ฅผ ํตํด ์ ๋ ฌ ๊ธฐ์ค์ ๋ง๋ค์ด์คฌ์ต๋๋ค.
์ดํ ์ ๋์จ ํ์ธ๋๋ฅผ ์ํด ์์ ์ ๋ฃจํธ ๋ ธ๋๋ฅผ ์ฐพ๋ ๋ฉ์๋(find)์ ์ด๋ฅผ ํฉ์ณ์ฃผ๋ ๋ฉ์๋(union)์ ์ ์ํ์ต๋๋ค. ์ด๋ฅผ ํตํด ๋ฃจํธ ๋ ธ๋๊ฐ ๊ฐ์ ๊ฒ๋ค์ ์ฐพ๊ณ ํต์ผํด์ค ์ ์์ต๋๋ค.
๋ง์ง๋ง์ผ๋ก Edge๋ฅผ ์ํํ๋ฉฐ ๋ฃจํธ๊ฐ ๋ค๋ฅธ ๊ฒฝ์ฐ ์ด๋ฅผ ๋น์ฉ์์ ๋ํด์ฃผ๊ณ ๋ฃจํธ๋ฅผ ํฉ์ณ์ฃผ๋ฉด ๋ฉ๋๋ค.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static int n, m;
static List<Edge> edges = new ArrayList<>();
static int[] parent;
public static void main(String[] args) throws Exception {
n = input.integer();
m = input.integer();
parent = new int[n + 1];
for (int index = 0; index < m; index++) {
int start = input.integer();
int end = input.integer();
int cost = input.integer();
edges.add(new Edge(start, end, cost));
}
Collections.sort(edges);
int answer = 0;
for (int index = 1; index <= n; index++) {
parent[index] = index;
}
for (Edge edge : edges) {
if (find(edge.start) != find(edge.end)) {
answer += edge.cost;
union(edge.start, edge.end);
}
}
System.out.println(answer);
}
public static int find(int x) {
if (x == parent[x]) {
return x;
}
return parent[x] = find(parent[x]);
}
public static void union(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
parent[y] = x;
}
}
static class Edge implements Comparable<Edge> {
int start;
int end;
int cost;
public 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;
}
}
static Input input = new Input();
static class Input {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer("");
public int integer() throws Exception {
if (!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
return Integer.parseInt(st.nextToken());
}
public String next() throws Exception {
if (!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
return st.nextToken();
}
public char[] nToCharArray() throws Exception {
if (!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
return st.nextToken().toCharArray();
}
}
}
'๐ PS > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
boj-1916 (0) | 2022.08.24 |
---|---|
boj-2252 (0) | 2022.08.22 |
boj-1850 (0) | 2022.07.23 |
boj-1744 ์ ๋ฌถ๊ธฐ (0) | 2022.07.15 |
boj-1300 K๋ฒ์งธ ์ (0) | 2022.07.14 |
๋๊ธ