유니온 파인드는 그룹을 묶고(union) 찾는(find) 방식이다.
- 먼저 부모 배열(parent)을 자기 자신으로 초기화 시켜준다.
parent = new int[N+1]; for(int i = 1; i <= N; i++) { parent[i] = i; }
- 같은 묶음으로 표시된 숫자들을 union 시켜준다.
(통상적으로 번호 작은쪽을 부모노드라고 함.)for(int i = 1; i <= N; i++) { st = new StringTokenizer(br.readLine(), " "); for(int j = 1; j <= N; j++) { if(Integer.parseInt(st.nextToken()) == 1) { unionParent(i, j); } } }
- 각 노드의 부모들을 거슬러 올라가며 찾아준다.
// 각 원소가 속한 집합 출력하기 System.out.print("각 원소가 속한 집합: "); for (int i = 1; i <= v; i++) { System.out.print(findParent(i) + " "); }
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if(a < b) {
parent[b] = a;
} else {
parent[a] = b;
}
}public static int findParent(int x) {
if(parent[x] == x) {
return x;
}
return parent[x] = findParent(parent[x]);
}1-1. [여행 계획] 문제
문제 워드 제공
https://minimun92.tistory.com/43
한울이가 사는 나라에는 N개의 여행지가 있으며, 각 여행지는 1 ~ N번 까지의 번호로 구분된다. 또한 임의의 두 여행지 사이에는 두 여행지를 연결하는 도로가 존재할 수 있다. 이때, 여행지가 도로로 연결되어 있다면 양방향으로 이동이 가능하다. 한울이는 하나의 옇애 계획을 세운 뒤에 이 여행 계획이 가능한지 여부를 판단하고자 한다. 예를들어 N=5이고, 다과 같이 도로의 정보가 주어진다
- 1번 - 2번
- 1번 - 4번
- 1번 - 5번
- 2번 - 3번
- 2번 - 4번
만약 한울이의 여행 계획이 2번 -> 3번 -> 4번 -> 3번 이라면, 2번 -> 3번 -> 2번 -> 4번 -> 2번 -> 3번의 순서로 여행지를 방문하면, 여행 계획을 따를 수 있다.
여행지의 개수와 여행지 간의 연결 정보가 주어졌을 때, 한울이의 여행 계획이 가능한지의 여부를 판별하는 프로그램을 작성하시오
입력 조건
여행지의 수 N, 여행 계획의 수 M (1 <= N,M <= 500)
다음 N개의 줄에 걸쳐 N x N 행렬을 통해 임의의 두 여행지가 서로 연결되어 있는지의 여부가 주어진다. 그 값이 1이라면 서로 연결되어 있다는 의미, 0이면 연결되어 있지 않다는 의미
마지막줄에는 여행 계획이 포함된 여행지의 번호들이 주어진다.
출력 조건
첫째 줄에 한울이의 여행 계획이 가능하다면 YES를, 불가능하다면 NO를 출력해라.
1-2. 풀이
유니온파인드를 사용하여 두 여행지가 서로 연결되어있다면 (이차원 배열 값이 1이라면) union을 수행한다.
그 이후 주어진 여행지 숫자들의 Parent 값이 같은지 확인해준다.
1-3. 코드
import java.util.*;
import java.io.*;
public class UnionFind_여행계획 {
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(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
parent = new int[N+1];
for(int i = 1; i <= N; i++) {
parent[i] = i;
}
for(int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j = 1; j <= N; j++) {
if(Integer.parseInt(st.nextToken()) == 1) {
unionParent(i, j);
}
}
}
st = new StringTokenizer(br.readLine(), " ");
int checkParent = findParent(Integer.parseInt(st.nextToken()));
boolean flag = true;
for(int i = 1; i < M; i++) {
if(checkParent != findParent(Integer.parseInt(st.nextToken()))) {
System.out.println("NO");
return;
}
}
System.out.println("YES");
}
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if(a < b) {
parent[b] = a;
} else {
parent[a] = b;
}
}
public static int findParent(int x) {
if(parent[x] == x) {
return x;
}
return parent[x] = findParent(parent[x]);
}
}
2-1. [집합의 표현] (백준 1717) 문제
https://www.acmicpc.net/problem/1717
2-3. 코드
import java.util.*;
import java.io.*;
public class Main {
static int[] parent;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int 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 check = Integer.parseInt(st.nextToken());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if(check == 0) { // 합집합
union(a, b);
} else { // a와 b가 같은 집합에 있는지 확인
if(findParent(a) == findParent(b)) {
sb.append("YES" + "\n");
} else {
sb.append("NO" + "\n");
}
}
}
System.out.println(sb.toString());
}
public static void union(int a, int b) {
a = findParent(a);
b = findParent(b);
if(a < b) {
parent[b] = a;
} else {
parent[a] = b;
}
}
public static int findParent(int x) {
if(parent[x] == x) {
return x;
} else {
return parent[x] = findParent(parent[x]);
}
}
}
