[코테] 백준 1717번 : 집합의 표현 (java)

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

알고리즘 분류 : 자료 구조, 분리 집합

❓문제

---

🔅해석

Union-Find의 기초 문제이다.

 

Union 연산은 어떤 두 원소 a, b에 대해서 각 원소가 속한 집합을 하나로 합치는 연산이다.

먼저 두 원소가 같은 집합인지 확인하고 같은 집합이 아니라면 하나로 합친다. 보통 같은 집합을 확인하는 과정은 부모의 번호를 기재하여 확인한다.

Find 연산은 어떤 원소 a에 대해서 a가 속한 집합(집합의 대표번호)을 반환한다.

 

문제의 예시를 아래와 같이 가정한다.

//input
7 4
0 1 3
1 1 7
0 7 6
1 1 3

 

 

1. 7 4

n개의 집합을 생성한다.

Initialize

 

각 집합의 부모는 자신을 가르키고있다.

 

2. 0 1 3

union

union(1,3)

1과 3에 대해 parent를 확인하고 같은 parent를 갖고 있지않다면 b의 집합을 a에 속하게 한다.(하나로 합친다.)

 

 

3. 1 1 7

find

1과 7의 부모를 확인한다. 1의 parent(=1) != 7의 parent(=7) 이므로 "NO"를 리턴한다.

 

4. 0 7 6

union

union(7, 6)

 

5. 1 1 3

find

1과 3의 부모를 확인한다. 1의 parent(=1) == 3의 parent(=1) 이므로 "YES"를 리턴한다.

 

---

⭕정답 코드

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

public class Main {

	static int N, M;
	static int[] parent;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		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 type = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			if (type == 0) {
				union(a, b);
			} else {
				int aParent = find(a);
				int bParent = find(b);
				if (aParent == bParent) {
					sb.append("YES").append("\n");
				} else {
					sb.append("NO").append("\n");
				}
			}
		}

		System.out.println(sb.toString());
		br.close();
	}

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

	private static void union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		if (aRoot != bRoot)
			parent[aRoot] = bRoot;

	}
}

 

---

❗결과