Union-Find 쉽게 이해하기

1. 개념
   1-1. 큰 개념
   1-2. Find
   1-3. Union
2. 로직
3. 코드

 

 

 

---

 

1. 개념

1-1. 큰 개념

 

1-2-3, 4-5-6 으로 연결된 그래프

 

위 그림과 같은 그래프가 있다고 하자.

1-2-3 이 연결되어 있고 4-5-6이 연결되어 있다.

"2랑 6은 서로 같은 그룹에 속해있나요?"라고 누군가 묻는다면 "아니요"라고 대답할 것이다.

질문을 받으면 우리 머릿속에서는 다음과 같은 계산이 이루어질 것이다.

"음... 2가 어디 있지? 그래 왼쪽 그룹에 있구나. 그러면 6은... 6은 오른쪽 그룹에 있네?"
"그러면 두 숫자는 서로 다른 그룹에 속해있구나!"

 

이와 같은 계산을 컴퓨터가 하려면 어떻게 해야 할까?

그게 바로 지금부터 설명할 Union-Find 알고리즘이다. 

 

 

1-2. Find

• 찾다라는 뜻을 가지고 있다.
• 어떤 원소가 속한 그룹을 반환한다.
  • 정확히는 그룹을 대표하는 원소를 반환한다.
• 속한 그룹을 비교하여 같은 그룹인지를 판단한다.

 

그래프 예시

 

Find는 그룹을 대표하는 원소를 반환하는 연산이다.

예를 들어 왼쪽 그룹을 대표하는 원소가 1이고

오른쪽 그룹을 대표하는 원소가 4라고 해보자.

그럼 이제부터 왼쪽 그룹은 1, 오른쪽 그룹은 4로 표현할 수 있는 것이다.

 

 

재석이가 있는 재석팀, 종국이가 있는 종국팀

 

쉽게 생각하면 이런 느낌이다.

재석이가 팀을 대표하니까 재석팀

종국이가 팀을 대표하니까 종국팀

 

아까 예시에서도

1이 그룹을 대표하니까 그룹을 1이라고 부르고

4가 그룹을 대표하니까 그룹을 4라고 부르는 것이다.

 

"지효야 너 무슨 팀이야? 재석팀이구나."
"광수야 너는 무슨 팀이야? 종국팀이구나."
"그러면 지효랑 광수는 서로 다른 팀에 속해있구나!"

[목차 1-1]에서 나눈 대화를 현실세계에 맞게 바꿔봤다.

이런 식으로 어떤 원소가 속한 그룹을 찾아내는 연산이 Find이다.

우선 개념만 알고 넘어가자. 자세한 로직은 이후에 이어진다.

 

 

1-2. Union

• 조합, 협회라는 뜻을 가지고 있다. 좀 더 쉬운 말로 그룹이라고 생각하자.
• 두 개의 그룹을 하나의 그룹으로 합치는 작업을 한다.

 

그래프 예시

 

여기 1부터 6까지의 숫자가 있다.

각각의 숫자들은 아직 그룹을 이루지 않은 상태이다.

즉, 1번은 그룹 1에 속해있고 2번은 그룹 2에 속해있고... 6번은 그룹 6에 속해있다고 봐도 무방하다.

그룹을 대표할 수 있는 원소가 자기 자신밖에 없기 때문이다.

 

다시 런닝맨에 대입해서 생각해보면

재석이가 팀원 없이 홀로 있다고 해보자. 그러면 어쩌겠어 재석팀이지.

종국이가 팀원 없이 홀로 있다고 해보자. 그러면 또 어쩌겠어 종국팀이지. 선택권이 없다.

 

 

 

1번과 2번이 그룹을 이룸

 

자 이제 1과 2를 하나의 그룹으로 묶어보자.

우리는 이 연산을 Union이라고 부른다.

어떤 원소를 대표로 설정할지는 나름의 규칙대로 정해주면 된다.

 

 

 

2. 로직

 

그래프의 관계를 나타낸 표

 

이제 개념을 이해했으니 Union, Find를 어떻게 이용해야 코드를 짤 수 있는지 알아보자.

 

그래프의 관계를 표로 나타내 보았다.

1번은 자기 자신을 가리키고

2번도 자기 자신을 가리키고

...

6번까지 동일하기 때문에 노드 번호와 부모 번호가 전부 같다.

 

 

1번과 2번을 Union 한 표

 

 

1번과 2번을 Union한 뒤 표의 변화이다.

1번 노드가 2번 노드의 부모가 되었기 때문에

2번 노드의 부모 노드 값을 1로 바꾸어 주었다.

 

 

2번과 3번을 Union 한 표

 

2번과 3번을 Union한 뒤 표의 변화이다.

2번 노드가 3번 노드의 부모가 되었기 때문에

3번 노드의 부모 노드 값을 2로 바꾸어 주었다.

 

여기서 슬슬 헷갈리고 의문점이 생긴다. (내가 그랬다)

아니.. 1번이 대표 원소라며? 2로 바꾸면 어떻게 해? 똑같이 1로 바꿔줘야 하는 거 아니야?

좋다. 그러면 2가 아니라 1로 바꾸면 어떻게 되는지 바로 다음에서 확인해보자.

 

 

3번의 부모를 1로 설정한 경우 (잘못된 예시)

 

3의 부모를 1로 설정해버리면 그래프 관계가 변형이 되어버린다.

원본을 유지할 수 없다는 것이다.

그렇다면 어떻게 해야 하나?

그래서 필요한 게 바로 Find이다.

 

2번과 3번을 Union 한 표

 

다시 아까 보던 그래프와 표를 보자.

3번의 부모는 2번이고 2번의 부모는 1번이다.

 

 

루트 노드(대표 원소)를 찾아가는 과정

 

우리는 부모 번호를 통해서 루트 노드(대표 원소)를 찾아갈 수 있다.

부모 번호를 이용해서 쭉쭉쭉 부모의 부모 부모의 부모 부모의 부모... 를 찾아가다가

노드 번호와 부모 번호가 같다면 "어? 네가 바로 루트 노드구나?"를 알 수 있는 것이다.

이 과정이 바로 Find이다.

 

 

	public static int find(int x) {
		if (root[x] == x) { // 노드 번호와 부모 번호가 같다면
			return x; // 루트 번호 찾았다!!
		} else {
			return find(root[x]); // 같지 않다면 부모 노드를 찾아감
		}
	}

코드를 보자면 위와 같다.

재귀로 아주 간단하게 작성할 수 있다.

 

 

Union을 다 한 표

 

Union을 다 한 다음에 [목차 1-1]에서 했던 질문을 다시 해보자.

"2랑 6은 서로 같은 그래프에 속해있나요?"

컴퓨터는 다음과 같은 순서로 연산해서 답을 내놓을 것이다.

2번 노드의 부모 노드 -> 1번 노드
1번 노드의 부모 노드 -> 1번 노드
---------------------------------------
즉, 2번 노드는 1번 그룹에 속함


6번 노드의 부모 노드 -> 5번 노드
5번 노드의 부모 노드 -> 4번 노드
4번 노드의 부모 노드 -> 4번 노드
---------------------------------------
즉, 6번 노드는 4번 그룹에 속함


따라서, 2와 6은 서로 다른 그룹에 속함

 

이제 이 로직을 코드로 구현해내면 된다.

 

 

3. 코드

 public static int find(int x) {
    if (root[x] == x) {
        return x;
    } else {
        return find(root[x]);
    }
}
    
 public static void union(int a, int b) {
    int rootA = find(a); // a의 루트 노드를 찾는다.
    int rootB = find(b); // b의 루트 노드를 찾는다.
 
    root[rootA] = rootB; // a의 루트 노드를 b의 루트 노드에 붙인다.
}

거창했던(?) 설명과 달리 코드는 다소 단조롭다.

포스팅을 한 번 읽는 거로는 절대 Union-Find를 온전히 이해할 수 없으니 문제를 하나 풀어보는 것이 좋다.

(문제 및 풀이 링크 추가 예정)

 

 

 

 

---

💡 느낀 점

• 서로소 집합(disjoint-set), 합집합-찾기(union-find), 병합-찾기 집합(merge-find set) 이렇게 3가지 이름으로 불린다고 한다. 왜 이렇게 이름이 많은 거여
• 2달 전쯤 문제 풀었을 때 이해했다고 생각했는데 어제 문제 풀 때 생각이 안 나서 2시간 동안 붙잡고 있었다. 코드를 보면 진짜 간단한데 생각해내긴 어려운 것 같다.
• union 코드에서 맨 마지막 줄, 그니까 한쪽의 루트 노드를 다른 한쪽의 루트 노드에 붙이는 작업을 실수해서 삽질을 오래 했다. root[a] = b 이렇게 하면 말단 노드를 말단 노드에 붙이는 셈이 된다.
• Kruskal 알고리즘에서도 Union-Find가 쓰이니 잘 알아두자.

---