https://www.acmicpc.net/problem/1717
알고리즘 유형
- 그래프
- 유니온 파인드
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class boj1717 {
static int n, m;
static int [] parent;
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; // i값으로 초기화
}
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int check = Integer.parseInt(st.nextToken());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if (check == 0) {
union(a,b);
}
else if (check == 1) {
check(a,b);
}
}
}
public static void check(int a, int b) {
a = find(a);
b = find(b);
if (a == b) {
System.out.println("YES");
}
else {
System.out.println("NO");
}
}
public static void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
parent[b] = a;
}
}
public static int find(int n) {
if (parent[n] == n) { // 배열 인덱스와 값이 같다면 해당 값 리턴
return n;
}
// System.out.println("find: " + find(parent[n]));
int m = find(parent[n]);
parent[n] = m;
return m;
}
}
회고
크루스칼 알고리즘과 프림 알고리즘을 풀기 전에, 유니온 파인드 알고리즘에 대한 이해가 선행되어야 했기 때문에 찾아서 공부했다.
유니온 파인드는 언제 사용될까?
서로 다른 2개의 원소가 같은 집합인지 여부를 체크할 때 사용된다. 유니온 파인드에는 union 메서드와 find 메서드가 존재하는데, 이 두개를 이해하는게 중요하다.
처음에 입력을 받을 때 1차원 배열에 각 노드의 번호를 값으로 입력 받는다.
int [] parent
1 | 2 | 3 | 4 | 5 | 6 |
1 | 2 | 3 | 4 | 5 | 6 |
find
특정 노드 n에 대해서 대표 노드를 리턴하는 함수
public static int find(int n) {
if (parent[n] == n) { // 배열 인덱스와 값이 같다면 해당 값 리턴
return n;
}
// System.out.println("find: " + find(parent[n]));
int m = find(parent[n]);
parent[n] = m;
return m;
}
배열의 인덱스와 값이 같다면 바로 리턴해주면 된다. ex) parent[1] = 1
하지만, 노드가 이렇게 연결되어 있다면,
1 | 2 | 3 |
1 | 1 | 2 |
이런식으로 배열이 표현될 것이다. (A,B,C가 1,2,3이라고 가정)
여기서 1과 3의 연결 여부는 어떻게 알 수 있을까?
재귀적으로 3의 대표 노드인 2를 리턴하고, 또 2는 대표 노드인 1을 리턴해서 최종적으로 1과 3이 연결되어 있음을 확인할 수 있다.
union
각 노드가 속한 집합을 하나로 합치는 함수
public static void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
parent[b] = a;
}
}
앞서 선언한 find 함수를 통해서 값을 가져오고, 두 개의 값이 다르다면 대표 노드를 바꿔준다.
일반적으로, 더 작은 쪽이 대표 노드가 된다.
'Algorithm > 백준' 카테고리의 다른 글
[백준] Gold IV. 케이크 자르기 (0) | 2024.09.05 |
---|---|
[백준] Gold IV. 여행 가자 (0) | 2024.08.02 |
[그래프] 위상정렬 (0) | 2024.07.29 |
[백준] Silver I. 절댓값 힙 (0) | 2024.07.23 |
[백준] Silver II. 생태학 (0) | 2024.07.22 |