Union-find
오랜만에 분리집합 문제를 풀게 되었는데 오답을 받게 되었다.
그 동안 union - find 로직에 대해 깊게 이해하지 않고 코드를 외우는 방식으로 공부했던 나 자신을 다시 바로 잡으려고 한다.
public static void union(int a, int b){
int fa = find(a);
int fb = find(b);
if(fa != fb){
if(fa < fb){
parent[b] = fa;
}else{
parent[a] = fb;
}
}
}if(fa < fb){
parent[**b**] = fa;
}else{
parent[**a**] = fb;
}실수했던 부분은 위와 같다.
먼저 union 이란 무엇인가?
집합의 대표 노드를 연결하는 것
why?
- 매개변수로 들어온 노드 a, b가 현재 가르키고 있는 각자의 그룹의 대표 노드를 하나로 일치시키는 함수
- 그러니 parent[ i ]의 값을 바꿔줘야 한다고 생각하여 위와 같은 코드를 작성했다.
if(fa < fb){
parent[fb] = fa;
}else{
parent[fa] = fb;
}위와 같은 코드로 수정하여 AC를 받을 수 있었다.
쉽게 이해하기 위해 만화 원피스를 예로들어 정리해 보았다.
현재 모든 인원들은 자신만의 해적단을 가지고 있고, 본인이 선장인 1인 해적단이라 가정한다.
이때 루피와 조로가 만나 해적단을 결성하려 한다.
둘은 하나의 그룹으로 묶여야한다.
이때 union(조로, 루피)가 필요하다.
union(조로, 루피){
조로해적단 선장 = find(조로)
루피해적단 선장 = find(루피)
당연히 조로 해적단의 선장은 조로이고, 루피 해적단의 선장은 루피이다.
하나로 묶인 그룹의 대표를 정할 필요가 생겼다.
우리는 간단히 가나다라 순으로 대표를 정하고자 하고 그렇게 루피가 선장이 된다.
해적[ 조로 ] = 루피
이를 통해 조로 해적단과 루피 해적단을 하나로 합치게 된다.
}
union을 통해 각각 총 2개의 그룹이 생겼다.
이후 마르코는 쵸파와 함께 하고 싶은 욕구가 생겼다.
union(마르고 ,쵸파){
find(마르코) = 흰수염
find(쵸파) = 루피
가나다라 순으로 루피가 빠르기 때문에
마르코쪽에 값을 바꿔야한다.
그러면 해적[마르코] = 루피로 해야할까?
답은 해적[흰수염] = 루피로 해야한다.
}
왜? 마르코는 일원일 뿐이고 흰수염이 진짜 대표이기 때문이다.
선장끼리 연결해야 해적단이 합쳐진다. 팀원을 바꾼다고 팀 전체가 바뀌진 않는다.
최종적으로 이런 구조를 띄게 된다.
마르코와 에이스는 여전히 흰수염을 대표로 삼고있고 흰수염의 대표는 루피가 된다.
이때 find(마르코)를 하게 되었을 때 비로소 다음과 같은 트리가 그려진다.
에이스도 마찬가지로 find(에이스)를 하게 되었을 때 루피 직속으로 들어가게 된다.
Find 함수의 동작 원리
public static int find(int x){
if(parent[x] == x) return x;
else return parent[x] = find(parent[x]);
}'알고리즘 with 자바 > 알고리즘' 카테고리의 다른 글
| 문자열 자르기 관련 함수 (0) | 2022.04.25 |
|---|---|
| 순열 (0) | 2021.09.15 |
| 멱집합 (0) | 2021.09.13 |
| Recursion의 응용 : n queen problem (0) | 2021.09.09 |
| Recursion의 응용 : Counting Cells in a Bob (0) | 2021.09.09 |
