문제
초기에 {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 를 출력해도 된다)
예제
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_BJ_1717_집합의표현 {
static int N,M;
static int [] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int [N+1];
for(int i=0;i<arr.length;i++) arr[i]=i;
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine()," ");
int o = Integer.parseInt(st.nextToken());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if(o==0) {
union(a,b);
}else {
if(find(a)==find(b)) sb.append("YES\n");
else sb.append("NO\n");
}
}
System.out.println(sb.toString());
}
public static int find(int x) {
if(arr[x]==x) return x;
return arr[x] = find(arr[x]);
}
public static void union(int a, int b) {
int aRoot = find(a);
int bRoot = find(b);
if(aRoot != bRoot) arr[aRoot] = bRoot;
}
}
|
cs |
풀이방법
두 원소가 같은 집합에 포함되어 있는지를 확인하는 문제였습니다.
변수 o 가 0일 경우에는 두 집합을 합친다는 의미이므로 union()메소드를 통해 각 각의 루트를 찾아 두 원소가 다른 집합일 경우에는 집합의 루트를 같게 해 "두 원소가 같은 집합에 포함되어있다" 라고 표현해주었습니다.
변수 o가 1일 경우에는 두 원소가 같은 집합에 포함되어 있는지 확인하기 위해 find()메소드를 통해 루트가 같은지 확인하여 만약 같다면 yes를, 다르다면 no를 출력해주었습니다.
'문제 > 백준' 카테고리의 다른 글
| 백준 1966번 프린터 큐 [JAVA] (0) | 2021.03.23 |
|---|---|
| 백준 7568번 덩치 [JAVA] (0) | 2021.03.23 |
| 백준 1976번 여행가자 [JAVA] (0) | 2021.03.22 |
| 백준 1991번 트리 순회 [JAVA] (0) | 2021.03.17 |
| 백준 12865번 평범한 배낭 [JAVA] (1) | 2021.03.17 |
