초기에 {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차원 배열을 사용하게 되고 정의한 배열은 다음과 같은 의미를 갖는다. parents[ 본인 노드 ] = 부모 노드 즉, 인덱스가 가리키는 요소값은 현재노드(인덱스)가 어떤 부모노드(요소값)에 연결돼있냐를 나타낸다. 이 배열을 사용하기위해 "parents[i] = i" 로초기화 시켜준다.
합치기.(Union) 처음엔 각 노드가 분리돼있을 것이다. 후에 문제의 입력값과 조건에 따라 각노드를 합쳐주는 작업이 필요하다. 예를들어, parents가 초기값일때 합칠노드가 1과 7이라면 parents[7] = 1 or parents[1] = 7 을 이용해 합쳐 줄수 있다. 초기값이 아닐땐 비슷한데 이따 푸는 방법에서 설명하도록 하겠다.
같은 집합에 있는가(같은 루트노드를 갖고있는가, Find) 노드들이 어느정도 합쳐져서 트리가 형성됐다면 내가 탐색하고자 하는 노드들이 같은 트리안에 있는지 검사를 해줘야한다. 이때 검사하는 방법은 간단하게 탐색하고자하는 노드들의 루트노드를 찾고 같은 루트노드라면 같은 트리안에 있는 것으로 판단하면 된다.
유니온 파인드 문제를 풀기위해선 기본적으로 위의 3가지를 구현할줄 알아야한다. 아래를 풀이를 보며 어떻게 구현하는지 보자.
풀이 과정
parents배열 생성 및 초기화
parents 배열 생성후 위와 같이 초기화를 시켜준다.
합치기(Union) 이에 대한 것은 문제에서 주어진 입력값을 갖고 예를 들어보겠다. 문제에선 n의 이하의 자연수 또는 0이 v1,v2 값으로 들어온다 했다. 따라서 1번과 같이 배열을 초기화해줬고 초기화 해준다음 후에 입력받은 값들로 parents배열을 바꿔주는 작업을 해보겠다.
초기값
i(본인)
0
1
2
3
4
5
6
7
parents[i](부모)
0
1
2
3
4
5
6
7
v1=1 / v2=3
i(본인)
0
1
2
3
4
5
6
7
parents[i](부모)
0
1
2
1
4
5
6
7
v1=7 / v2=6
i(본인)
0
1
2
3
4
5
6
7
parents[i](부모)
0
1
2
1
4
5
6
6
v1=3 / v2=7
i(본인)
0
1
2
3
4
5
6
7
parents[i](부모)
0
1
2
1
4
5
1
6
v1=4 / v2=2
i(본인)
0
1
2
3
4
5
6
7
parents[i](부모)
0
1
2
1
2
5
1
6
v1=1 / v2=1
i(본인)
0
1
2
3
4
5
6
7
parents[i](부모)
0
1
2
1
2
5
1
6
위의 표에서 빨간색 숫자들이 Union로직을 통해 바뀐 부모노드들이다. 이에 대한 로직은 아래와같다.
같은 루트노드를 갖고 있는지 찾기(Find) 이부분은 간단하게 v1,v2노드가 같은 루트노드를 갖고 있는지 검사하기만 하면된다. 따라서 위에서 봤던 find함수를 이용해 각노드의 루트노드를 찾고 루트노드가 같은지 아닌지 판단만 해주면된다.
위의 과정을 통해 문제를 풀수 있다.
아래 전체 코드를보고 이해해보자.
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[] parents;//parents[본인노드] = 부모노드
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
parents = new int[N+1];
//배열을 각각의 노드가 본인이 부모노드가 되도록 초기화
for(int i=1; i<=N; i++) {
parents[i] = i;
}
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int com = Integer.parseInt(st.nextToken());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
if(com==0) {//두개 노드 합치기
union(v1,v2);
}else if(com==1) {//같은 루트노드에서 파생된 자식노드인지 판단
sb.append(sameP(v1,v2)).append("\n");
}
}
System.out.println(sb);
}
//두개 노드 합치기 == 같은 루트노드 갖도록하는 작업(트리합치기)
public static void union(int v1, int v2) {
v1 = find(v1);//v1의 루트노드 찾기
v2 = find(v2);//v2의 루트노드 찾기
/*
* 두개의 루트노드중 더작은 루트노드를
* 합치고 나서 한개의 루트노드로 갖도록 하는건데
* 사실 if(v1 != v2) parents[v2] = v1;
* 이거만 해도됨.
*/
if(v1 < v2) parents[v2] = v1;
else if(v1 > v2) parents[v1] = v2;
}
//두개의 노드가 하나의 루트노드에서 파생된 노드인지 검사(같은 루트노드 갖고있냐)
public static String sameP(int v1, int v2) {
v1 = find(v1);
v2 = find(v2);
if(v1==v2) {
return "YES";
}
return "NO";
}
//num가 루트노드로 뭘갖고 있는지 찾음.
public static int find(int num) {
//인덱스와 요소값이 같다는것은
//본인노드 == 루트노드 라는 말.
if(parents[num]==num) return num;
/*
* 인덱스와 요소값이 다를땐
* 재귀를 통해 요소값에 해당하는 부모노드를 하나씩 찾아가면서
* 최종적으로 처음에 알고싶어 했던 노드의 루트노드가 뭔지 찾음.
*/
return parents[num] = find(parents[num]);
}
}
마치며
유니온 파인드 알고리즘에 대해 공부 해볼 수 있었던 문제이다. 이번 문제는 다른 블로그를 참고해 풀고 이해했지만 해당 알고리즘에 대해 연습이 더 필요할듯 하다.
