집합의 표현
문제
초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.
집합을 표현하는 프로그램을 작성하시오.
입력
첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.
출력
1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)
풀이
문제 설명에서부터 유니온파인드 알고리즘을 사용하라고 알려주고 있다.
유니온 파인드는 말 그대로 유니온(합집합 연산)과 파인드(집합에 포함되어 있는지를 학인)로 이루어져 있다.
구현하는 방법은 합집합 연산을 할때 특정 수가 다른 특정 수를 가르키고 있는 방법을 사용하면 된다.
예를 들어 parent[] 배열을 선언 후 초기에는 자기 자신을 가르키도록 초기화한다.
합집합 연산을 진행할 때 특정 수 a가 가르키는 parent[a]를 b로 설정하도록 한다.
그러나 만약 합집합 연산이 많아진다면 연관관계가 복잡해짐으로 팀을 찾기가 어려워진다.
이를 해결하기 위해 각 팀은 대표값을 가르키도록 설정한다.
이는 자신이 가르키는 노드의 최상단 가르키는 노드를 가르키는 노드로 설정하는 것이다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
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());
int[] parent = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
parent[i] = i;
}
StringBuilder sb = new StringBuilder();
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());
if (a == 0) {
union(parent, b, c);
}else{
if (find(parent, b) == find(parent, c)) {
sb.append("YES").append("\n");
} else {
sb.append("NO").append("\n");
}
}
}
System.out.println(sb);
}
static int find(int[] parent, int n) {
if(parent[n] != n){
parent[n] = find(parent, parent[n]);
}
return parent[n];
}
static void union(int[] parent, int a, int b) {
a = find(parent, a);
b = find(parent, b);
if(a < b){
parent[b] = a;
}else{
parent[a] = b;
}
}
}
'알고리즘' 카테고리의 다른 글
1197 최소 스패닝 트리(Java) (0) | 2022.04.01 |
---|---|
12865 평범한 배낭 (JAVA) (0) | 2022.03.31 |
[프로그래머스] 신규 아이디 추천 (java) (0) | 2022.03.27 |
[프로그래머스] 신고 결과 받기 (java) (0) | 2022.03.27 |
[프로그래머스] 숫자 문자열과 영단어 (java) (0) | 2022.03.27 |