[java][boj][g4] 1717. 집합의 표현

1717번: 집합의 표현

문제

초기에 {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. n m
 * 2. m개의 줄에 각각의 연산 주어짐
 * 출력
 * 1. 1로 시작하는 입력에 대해서 YES/NO로 결과 출력
 * 조건
 * 1. 합집합은 0 a b
 * 2. 같은 집합에 포함되어 있는지를 확인 1 a b
 * 
 * 유니온 파인드
 * >> 부모가 같은지 확인한다
 * >> 재귀 이용
 */

유니온 파인드의 기본이 되는 문제다 재귀를 이용해 각 노드의 부모 노드가 같은지 확인하면 된다 부모 노드를 확인하는 findParent 함수, 부모 노드가 같은지 확인하는 isSameParent 함수, 합집합을 만드는 union 함수를 사용했다

코드

package lv28_유니온파인드;

import java.io.*;
import java.util.*;

public class g4_1717_집합의표현 {
	static int n, m;
	static int[] parent;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		parent = new int[n+1];
		
		for(int i = 1; i<=n; i++) {
			parent[i] = i;
		}
		
		for(int i = 0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int sw = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			if(sw == 0) union(x, y);
			else sb.append(isSameParent(x, y)).append("\n");
		}
		
		System.out.println(sb);
	}
	
	private static int findParent(int x) {
		if(x==parent[x]) return x;
		else return parent[x] = findParent(parent[x]);
	}

	private static String isSameParent(int x, int y) {
		x = findParent(x);
		y = findParent(y);
		
		if(x==y) return "YES";
		else return "NO";
	}

	private static void union(int x, int y) {
		x = findParent(x);
		y = findParent(y);
		
		if(x!=y) {
			if(x<y) parent[y] = x;
			else parent[x]=y;
		}
		
	}

}

결과

 

#자바 #java #boj #백준 #알고리즘