[백준 1717] 집합의 표현

글에 개요

백준 알고리즘 1717번 "집합의 표현" 문제입니다.

앞서 다루었던, 아래 참고할 글 1번에 정리한 내용을 보시면 쉽게 푸실 수 있는 문제입니다.

유니온 파인드 (Union-Find)를 정리한 글 내용을 꼭 보시길 추천드립니다!!!!

이 후 이 문제를 통해 확장할 수 있는 알고리즘이 많기 때문에 더더욱 익히셨으면 좋겠습니다. 

[백준 1717] 줄 세우기: https://www.acmicpc.net/problem/1717

참고할 글

1. http://brenden.tistory.com/33 ([알고리즘] 유니온 파인드(Union-Find) 정리글)

핵심 내용

1. 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다.
2. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행해야 한다.
3. Disjoint-set 자료구조를 구현하는 문제입니다.

해결 방법

1. parent[] 배열을 초기화 해줍니다.
2. find(), union(), isSameParent() 메소드를 만들어 줍니다.
3. 여기서 isSameParent()는 임의의 이름으로 만든 함수명입니다. find(), union() 메소드의 작동 원리만 파악하셔도 충분히 푸실 수 있는 문제입니다.

해결한 코드

	import java.util.Scanner;
	public class Main {
	public static int[] parent;
	public static int find(int x) {
	if(x == parent[x])
	return x;
	else
	return parent[x] = find(parent[x]);
	}
	public static void union(int x, int y) {
	x = find(x);
	y = find(y);
	if(x != y) {
	parent[y] = x;
	}
	}
	public static void isSameParent(int x, int y) {
	x = find(x);
	y = find(y);
	if(x == y) {
	System.out.println("YES");
	} else {
	System.out.println("NO");
	}
	}
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int m = sc.nextInt();
	parent = new int[n+1];
	for(int i = 0; i <= n; i++) {
	parent[i] = i;
	}
	for(int i = 0; i < m; i++) {
	int a = sc.nextInt();
	int x = sc.nextInt();
	int y = sc.nextInt();
	if(a == 0) {
	union(x,y);
	} else {
	isSameParent(x, y);
	}
	}
	}
	}

view raw B_1717.java hosted with ❤ by GitHub

백준 참고 내용

집합의 표현 성공 스페셜 저지

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	9173	3012	1978	30.586%

문제

초기에 {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 

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

예제 출력 1 

NO
NO
YES