[BaekJoon] 1717 집합의 표현 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/1717

2.  문제

요약

• 초기에 {0}, {1}, {2}, ..., {n}이 각각 n + 1개의 집합을 이루고 있습니다.
• 여기에 합집합 연산과 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 합니다.
• 여러 연산들이 주어질 때, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산에 대한 결과를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000,000보다 작거나 같은 n과 1보다 크거나 같고 100,000보다 작거나 같은 입력으로 주어지는 연산의 개수 m이 주어지고 두 번째 줄부터 m개의 줄에는 각각의 연산이 주어집니다. 합집합은 0 a b의 형태로 입력이 주어지고 이는 a가 포함되어 있는 집합과 b가 포함되어 있는 집합을 합친다는 의미입니다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어지고 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산입니다.
  • a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있습니다.
• 출력: 1로 시작하는 연산에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	static int[] parents;
	public int find(int num) { // num의 부모가 누구인지를 찾는 함수
		if(parents[num] == num) {
			return num;
		}
		return parents[num] = find(parents[num]);
	}
	
	public void union(int n1, int n2) { // n2의 부모가 n1의 부모보다 클 경우, n2의 부모를 n1의 부모로 치환하는 함수(n1의 부모가 n2의 부모보다 크다면 반대)
		int n1_position = find(n1);
		int n2_position = find(n2);
		if(n1_position != n2_position) {
			if(n1_position < n2_position) {
				parents[n2_position] = n1_position;
			} else {
				parents[n1_position] = n2_position;
			}
		}
	}
	
	public boolean isSameParent(int n1, int n2) {
		int n1_position = find(n1);
		int n2_position = find(n2);
		if(n1_position == n2_position) {
			return true;
		}
		return false;
	}
	
	public String[] getOperResult(String[] opers, int one_num) {
		for(int i = 0; i < parents.length; i++) {
			parents[i] = i;
		}
		String[] result = new String[one_num];
		int idx = 0;
		for(int i = 0; i < opers.length; i++) {
			String[] oper = opers[i].split(" ");
			int oper_type = Integer.parseInt(oper[0]);
			int n1 = Integer.parseInt(oper[1]);
			int n2 = Integer.parseInt(oper[2]);
			if(oper_type == 0) {
				union(n1, n2);
			} else if(oper_type == 1) {
				if(isSameParent(n1, n2)) {
					result[idx] = "YES";
				} else {
					result[idx] = "NO";
				}
				idx++;
			}
		}
		return result;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int n = Integer.parseInt(input[0]);
		int oper_num = Integer.parseInt(input[1]);
		parents = new int[n + 1];
		String[] opers = new String[oper_num];
		int one_num = 0;
		for(int i = 0; i < oper_num; i++) {
			opers[i] = br.readLine();
			if(opers[i].charAt(0) == '1')
				one_num++;
		}
		br.close();
		Main m = new Main();
		String[] result = m.getOperResult(opers, one_num);
		for(String s : result) {
			bw.write(s + "\n");
		}
		bw.flush();
		bw.close();
	}
}

4.  접근

• Union-Find 알고리즘을 이용하여 해당 문제를 해결합니다.
• Union-Find 알고리즘은 아래의 링크에서 확인하실 수 있습니다.

  Union-Find 알고리즘

• 간단하게 말하면 각 노드에 대해서 자신의 부모가 어떤 노드인지를 설정해주는 것을 의미합니다.

• 각 노드의 부모가 누구인지를 나타내는 배열 parents를 생성하고 자기 자신으로 초기값을 설정합니다.
• 주어진 각 연산들을 돌면서 만약 합집합 연산이면 합집합 연산을 진행합니다.
  • 주어진 두 수의 부모를 찾아 부모가 더 큰 쪽의 부모를 다른 수의 부모로 치환합니다.
• 만약 같은 집합에 포함되어 있는지 확인하는 연산이라면 해당 연산을 수행합니다.
  • 주어진 두 수의 부모를 확인하여 같다면 같은 집합에 있는 것이기 때문에 YES를, 그렇지 않다면 NO를 출력합니다.
• 어떠한 수의 부모를 확인할 때는 해당 수의 상위에 있는 부모들의 parents 값을 재귀함수를 통해 가장 상위의 부모로 변경합니다.