[자바] 백준 1717 - 집합의 표현

유니온 파인드 문제

 

1. 내 부모가 누구인지 담는 배열 parent[i]을 일단 나 자신으로 초기화 한다. 

 

2. 파인드

- 내 부모가 정말 최상위 부모인지 계속 찾아 나가면서, 최상위가 아닐 때에는 상위의 부모로 값을 교체한다. 

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

3. 유니온

- 두 숫자의 부모를 확인해서, 부모 값이 다르다면 부모 값을 a나 b의 부모값으로 교체해준다. 어떤 값의 부모를 넣을 것인지는 상관없다. 

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

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	static int[] parent;
	static int n;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] str = br.readLine().trim().split(" ");
		n = Integer.parseInt(str[0]);
		int m = Integer.parseInt(str[1]);
		
		parent = new int[n+1];
		for(int i=0;i<=n;i++) {
			parent[i] = i;
		}
		
		int k, a,b;
		for(int x=0;x<m;x++) {
			str = br.readLine().trim().split(" ");
			
			k = Integer.parseInt(str[0]);
			a = Integer.parseInt(str[1]);
			b = Integer.parseInt(str[2]);
			
			switch (k) {
			case 0:
				union(a,b);
				break;

			case 1:
				if( find(a) == find(b) ) sb.append("YES\n");
				else sb.append("NO\n");
				break;
			}
		}
		System.out.println(sb.toString().trim());

	}

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

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

---

처음에는 부모값을 바꿔주어야 할 때, 기존 부모값과 같은 부모를 가진 모든 자식들을 찾아서 부모값을 바꿔주려고 했다. 예를 들어  parent[7] = 1이고, 부모값을 6으로 바꿔주어야 하는 상황에서 부모값을 1로 가지는 모든 자식을 찾으려고 매번 for문을 돌렸더니 약간 당연하게도 시간초과가 났다. 근데 생각해보니 굳이 for문을 돌려서 다 바꿔줄 필요가 없었다. 

 

 

문제의 예시로 확인해보면 아래와 같다. 

(예시에서는 유니온 시에 a와 b 중 a의 부모값으로 통일시켜준다. )

 

0) 초기 parent 배열

원래 각자 자기 자신으로 세팅되어 있다.

나	1	2	3	4	5	6	7
부모값	1	2	3	4	5	6	7

 

1) 0 1 3

3의 부모값이 1로 바뀐다.

나	1	2	3	4	5	6	7
부모값	1	2	1	4	5	6	7

 

2) 0 7 6

6의 부모값이 7로 바뀐다.

나	1	2	3	4	5	6	7
부모값	1	2	1	4	5	7	7

 

3) 0 3 7

7의 부모값이 1로 바뀐다. 

나	1	2	3	4	5	6	7
부모값	1	2	1	4	5	7	1

이런 상황에서 3과 6이 같은 집합인지 물어봤을 때, parent[3]=1이고 parent[6]=7이니까 당연히 못 찾을 거라고 생각했다. 하지만 find()로직을 보면 parent[x]=x, 즉 나와 부모값이 같을 때에만 x값을 리턴하고 그렇지 않은 경우에는 다시 find()를 호출해서 그 결과값을 parent[x]에 집어넣게 되어있다. 

다시 말해, find(6)을 하면 아래 순서에 따라서 결국 parent[6]=parent[7]=parent[1]=1이 된다. 어차피 나와 부모값이 같을 때까지 find()에서 타고타고 내려가기 때문에 매번 for문 통해서 부모값을 바꿔줄 필요도 없고, 마찬가지 이유로 a랑 b의 부모값중 어떤 부모값을 선택해도 상관이 없다. 

호출순서
3	return parent[1]=1	//parent[x]=x이기 때문에 1을 리턴한다
2	else return parent[7]=find(parent[1])	//여기서 parent[7]=1로 값이 교체된다
1	else return parent[6]=find(parent[6])                                   =7	//여기서 parent[6]의 값도 1로 교체된다

전체코드