[BOJ] 1922 네트워크 연결
크루스칼 예제
문제
https://www.acmicpc.net/problem/1922
문제 풀이
package Baekjoon.Graph;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/**
* Created by kyeahen.
* Title : 1922 네트워크 연결
* Category : 그래프, 크루스칼 알고리즘
* Date: 2021/05/26
* ref - https://brenden.tistory.com/36 (크루스칼 알고리즘)
- https://blog.naver.com/ndb796/221230994142 (크루스칼 알고리즘)
*/
public class BJ_1922 {
static class Edge implements Comparable<Edge>{
int v1;
int v2;
int cost;
Edge(int v1, int v2, int cost) {
this.v1 = v1;
this.v2 = v2;
this.cost = cost;
}
@Override
public int compareTo(Edge o) { //오름차순 (비용)
return cost - o.cost;
}
@Override
public String toString() {
return "Edge{" +
"v1=" + v1 +
", v2=" + v2 +
", cost=" + cost +
'}';
}
}
static int N, M;
static ArrayList<Edge> edgeList;
static int[] parent;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine()); //컴퓨터 수
M = Integer.parseInt(br.readLine()); //연결할 수 있는 선의 수
edgeList = new ArrayList<>();
parent = new int[N + 1];
StringTokenizer st;
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()); //비용
edgeList.add(new Edge(a, b, c));
}
//각 노드가 자기 자신을 루트 노드로 갖도록 초기화
for (int i = 1; i <= N; i++) {
parent[i] = i;
}
Collections.sort(edgeList);
int sum = 0;
for (int i = 0; i < edgeList.size(); i++) {
Edge e = edgeList.get(i);
//동일한 루트 노드를 같지 않는 경우, 사이클이 발생하지 않을 때만 선택
if (!isSameParent(e.v1, e.v2)) {
sum += e.cost;
union(e.v1, e.v2);
}
}
System.out.println(sum);
}
//union
// - 두개의 집합을 하나의 집합으로 합친다.
public static void union(int x, int y) {
x = find(x); //x의 루트 노드 찾기
y = find(y); //y의 루트 노드 찾기
if (x != y) { //x와 y가 같은 노드가 아니면
parent[y] = x; //y의 루트 노드를 x로 갱신
}
}
//find
// - 원소가 주어졌을 때, 원소의 루트노드 반환
public static int find(int x) {
if (parent[x] == x) { //x의 루트 노드가 자신이면 자기 자신 반환
return x;
}
return parent[x] = find(parent[x]); //x의 루트 노드의 루트노드 찾아서 반환
}
//루트 노드가 같은지 체크
public static boolean isSameParent(int x, int y) {
x = find(x);
y = find(y);
if (x == y) { //같은 루트 노드이면
return true;
}
return false;
}
}
TMI
21/06/16: 알고리즘 스터디 문제 풀이🤓
댓글남기기