[알고리즘] 백준 1717 : 집합의 표현 - JAVA

문제

---

 

1717번: 집합의 표현

문제설명

초기에 n+1개의 집합 {0},{1},{2},…,{n}이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

 

입력

첫째 줄에 n, m이 주어진다. m은 입력으로 주어지는 연산의 개수이다.

다음 m개의 줄에는 각각의 연산이 주어진다.

합집합은 0 a b의 형태로 입력이 주어진다.

이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다.

두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다.

이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다

 

출력

1로 시작하는 입력에 대해서 a와 b가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.

 

 

풀이

---

해당 문제는 0이면 합집합 연산을, 1이면 같은 집합인지 확인하는 연산을 수행하는 문제입니다. 

 

때문에 합집합 찾기에 유용한 Unoin-Find 알고리즘을 이용하여 쉽게 풀이할 수 있습니다.

 

0 이면 union, 1이면 a와 b 를 find하여 각 집합을 대표하는 값을 받아와 같은지 체크하여 풀이할 수 있습니다.

 

Union-Find에 대한 설명은 아래의 링크에서 확인할 수 있습니다.

유니온 파인드 (Union-Find)

 

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_1717_집합의표현 {
	static int[] parents;
	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];
		for(int i = 1; i <= N; i++) { // 각 집합은 자신을 가르킬 수 있도록 초기화
			parents[i] = i;
		}
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int c = Integer.parseInt(st.nextToken()); // 명령값
			int a = Integer.parseInt(st.nextToken()); 
			int b = Integer.parseInt(st.nextToken());
			
			if(c == 0) union(a, b); // 명령값이 0이면 union
			if(c == 1) { // 명령값이 1이면 find후 체크
				if(find(a) == find(b))System.out.println("YES"); // 같은 집합이면 yes
				else System.out.println("NO"); // 다른 집합이면 no
			}
		}
	}
	
	public static void union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		if(aRoot == bRoot)return; // 같은 집합이라면 종료
		
		parents[bRoot] = parents[aRoot]; // 다른 집합이라면 b의 대표값을 a의 대표값으로 수정
	}

	private static int find(int a) {
		if(a == parents[a])return a;
		return parents[a] = find(parents[a]);
	}
}