[백준] 단계별로 풀어보기(단계:30, 유니온 파인드,JAVA)1717번, 집합의 표현

문제 링크

1717번: 집합의 표현

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

유니온 파인드

 상호 배타적으로 이루어진 집합을 효율적으로 표현하기 위해 만들어진 자료구조

Union : 집합끼리 합치는 연산

Find : 집합의 원소가 어디에 속해있는지 확인하는 연산

Union Find - 나무위키

이 문제에 핵심은

1. {0}...{n+1}의 집합 n+1개가 존재한다.

2. 0은 합집합, 1은 교집합 명령어이다.

3. 명령어와 a, b가 주어지며 교집합을 할 때 존재하면 YES, 존재하지 않으면 NO가 출력된다.

 

예제입력1에서 유니온파인드가 어떻게 진행되는지 보여드리겠습니다.

 

※저는 합집합을 진행할 때 집합의 루트 노드가 더 작은 곳을 루트 노드로 하였습니다.

 

 

빨간색 : 해당 원소의 루트 노드

0	1	2	3	4	5	6	7
0	1	2	3	4	5	6	7

 

입력값 : 0 1 3

해석 : 집합 1과 집합 3을 합집합!

0	1	2	3	4	5	6	7
0	1	2	1	4	5	6	7

집합 1과 집합 3의 루트 노드를 비교하여 더 작은 루트 노드로 통합합니다.

 

입력값 : 1 1 7

해석 : 집합 1과 집합 7이 교집하는지?

0	1	2	3	4	5	6	7
0	1	2	1	4	5	6	7

집합 1과 집합 7의 루트 노드가 다르기 때문에 교집하지 않는다.

출력 : NO

 

입력값 : 0 7 6

해석 : 집합 7과 집합 6을 합집합!

0	1	2	3	4	5	6	7
0	1	2	1	4	5	6	6

집합 7과 집합 6의 루트 노드를 비교하여 더 작은 루트 노드로 통합합니다.

 

입력값 : 1 7 1

해석 : 집합 1과 집합 7이 교집하는지?

0	1	2	3	4	5	6	7
0	1	2	1	4	5	6	6

집합 1과 집합 7의 루트 노드가 다르기 때문에 교집하지 않는다.

출력 : NO

 

입력값 : 0 3 7

해석 : 집합 3과 집합 7을 합집합!

0	1	2	3	4	5	6	7
0	1	2	1	4	5	1	6

집합 3과 집합 7의 루트 노드를 비교하여 더 작은 루트 노드로 통합합니다.

집합 7의 루트노드 6과 통합되어 집합 6의 루트 노드가 변경됩니다.

집합 1의 형태는

 

입력값 : 0 4 2

해석 : 집합 4과 집합 2을 합집합!

0	1	2	3	4	5	6	7
0	1	2	1	2	5	1	6

집합 2과 집합 4의 루트 노드를 비교하여 더 작은 루트 노드로 통합합니다.

 

입력값 : 0 1 1

해석 : 집합 1과 집합 1을 합집합!

0	1	2	3	4	5	6	7
0	1	2	1	2	5	1	6

집합 1과 집합 1은 같은 집합으로 아무일도 일어나지 않는다.

 

입력값 : 1 1 1

해석 : 집합 1과 집합 1이 교집하는지?

0	1	2	3	4	5	6	7
0	1	2	1	4	5	6	6

집합 1과 집합 1은 같은 집합으로 당연히 교집한다.

만약 집합이 서로 다르지만 루트 노드가 같다면 그 두 집합은 교집한다고 표현한다.

 

출력 : YES

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 사용하여 n,m과 명령어에 대한 정보를 저장합니다.
• 명령어에 따라 union함수와 isCheck함수를 실행하였습니다.
• BufferedWriter에 isCheck의 결과가 저장된 StringBuilder를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• find는 재귀탐색을 이용하여 루트 노드의 값을 찾는 함수입니다.
• union은 두 집합의 루트 노드의 값을 얻어서 더 작은 값으로 통합하는 함수입니다.
• isCheck은 두 집합의 루트 노드의 값이 같은지 확인하여 교집하는지 확인하는 함수입니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main {
	static int n,m;
	static int[] num;		//숫자의 루트노드 저장 배열
	static StringBuilder sb = new StringBuilder();	//결과 StringBuilder
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		num = new int[n+1];
        	//0~n+1집합 루트노드 설정
		for(int i=0;i<=n;i++)
			num[i] = i;
        	//명령어 수행
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine()," ");
			int command = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if(command==0) 	//0, 합집합
				union(a,b);
			else		//1, 교집합
				isCheck(a,b);
		}
		bw.write(sb.toString());		//결과 BufferedWriter 저장
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//루트 노드의 값 찾기 함수
	static int find(int n) {
		if(n==num[n])
			return n;
		return num[n] = find(num[n]);
	}
    	//루트 노드 값이 더 작은 값으로 합치는 함수
	static void union(int a, int b) {
		int x = find(a);
		int y = find(b);
		
		if(x!=y) {
			if(x>y)
				num[y] = x;
			else
				num[x] = y;
		}
		return;
	}
    	//두 집합의 루트노드가 같은지 확인하는 함수
	static void isCheck(int a, int b) {
		int x = find(a);
		int y = find(b);
		if(x==y)
			sb.append("YES\n");
		else
			sb.append("NO\n");
		return;
	}
}