[BOJ] 1717.집합의 표현
백준 알고리즘 문제 풀이
해당 문제는 union, find 라는 알고리즘 기법을 활용하여 풀어보았습니다.
링크 : 
1. 문제
문제 보기
| 시간 제한 | 메모리 제한 |
|---|---|
| 2 초 | 128 MB |
초기에 {0}, {1}, {2}, … {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.
집합을 표현하는 프로그램을 작성하시오.
입력(Input)
첫째 줄에 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이며 같을 수도 있다.
출력(Output)
1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)
2. 문제 풀이
이 문제는 이전에 SSAFY를 다니면서 알고리즘 수업 시간에 배웠던 union, find 방법을 활용해서 문제를 풀어볼 수 있었다.
오랜된 기억이라서 처음에는 헤매기도 했지만 정리해둔 내용을 다시 생각해보며 더듬어가면서 풀었다.
union, find 방법에 대해서 다시 한 번 정리하자면 체크 할 멤버들의 수의 배열에 해당 연관이 있는지 표시를 하고, 같은 그룹인지 아닌지 확인 할 수 있는 방법이다.
이 문제에서의 조건은 0 입력이 들어오면 find로 찾아서 union으로 묶고, 1 입력이 들어오면 find로 찾아서 표출해 주라고 한다.
[0][1][2][3][4][5]
-1 -1 -1 -1 -1 -1
처음에는 그룹이 없다고 하여 위와 같이 세팅을 한다.
부모 배열을 선언하고 union, find의 방법을 각각 정의 한다.
union은 같은 그룹인지 먼저 찾아봐야 하므로 find를 먼저 정의해보자.
찾고자하는 수의 배열 위치를 확인하여 해당 그룹이 존재하면 재귀의 방법으로 최종 root를 찾는다.
[0][1][2][3][4][5]
-1 -1 -1 1 -1 3
find(5);
-> 5를 find 하면 해당 부모 배열에서 3을 찾을 수 있다.
그러면 3을 다시 find한다.
find(3)
-> 3을 find 하면 부모 배열에서 1을 찾을 수 있다.
그러면 1을 다시 find한다.
find(1)
-> 1을 find하면 -1 즉, 최상단 부모라는 뜻이된다.
그러면 1-3-5 의 트리와 같은 구조로 그룹을 그려 볼 수 있게 된다.
위와 같이 find의 방법을 설명했다면 이번에는 union을 알아본다.
[0][1][2][3][4][5]
-1 -1 -1 1 2 3
union(4, 5)가 되면 각각의 4와 5의 최상단을 find로 찾아낸다.
find(5) => 1 || find(4) => 2
가 되는 것을 볼 수 있다.
이 둘은 다른 그룹이기 때문에 합칠 수 있다.
각각의 루트를 찾았기 때문에 이제 어느 한 쪽의 루트를 다른쪽의 루트의 자식으로 넣어주기만 하면 된다.
1을 2의 자식으로 넣게되면 parents[1] = 2 가 되겠다.
그러면 결국 union 후의 모습은 논리적으로 아래와 같을 것이다.
[0] [1] [2] [3] : depth
2 - 1 - 3 - 5
- 4
이러한 방식을 이용하여 집합을 표현하고 묶어줄 수 있다.
그럼 이것을 활용하여 코드로 표현해보자.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class SetRepre_1717 {
static int[] parents;
private static boolean union(int a, int b) {
int aRoot = find(a);
int bRoot = find(b);
if(aRoot != bRoot) {
parents[bRoot] = aRoot;
return true;
}
return false;
}
private static int find(int a) {
if(parents[a] < 0) return a;
return parents[a] = find(parents[a]);
}
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());
parents = new int[n + 1];
Arrays.fill(parents, -1);
for(int i = 0; i < m; i++) {
if(!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
// 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미
int condition = Integer.parseInt(st.nextToken());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if(condition == 0) {
union(a, b);
} else { // 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b
if(find(a) == find(b)) System.out.println("YES");
else System.out.println("NO");
}
}
}
}
