Union-Find
'합집합-찾기' 알고리즘은 집합에 관한 알고리즘이다.
Find : 어떠한 요소가 어떤 집합에 속해있는지를 찾는 과정이다.
Union : 요소들을 하나의 집합에 합하는 과정이다.
Union-find 알고리즘이 시행되고 나면, 모든 요소들은 특정한 집합에 속하게 된다. 이를 바탕으로 '서로소 집합은 총 몇개?' 등을 묻게 된다.
집합과 트리의 관계
어떤 집합에서 가장 작은 수를 '루트'라고 불러보자.
3개의 서로소 집합인 경우 3개의 루트가 있다.
각각의 요소를 '노드'라고 하고,
각각의 노드끼리 같은 집합에 속하면 '링크'로 연결하고,
링크 중 더 작은 수를 '부모'라고 한다.
루트 노드는 자기 자신과 연결되게 되고, 이 경우의 링크를 갯수에 포함하지 않으면, n개의 노드를 가진 집합의 링크는 n-1개가 된다.
결과적으로, '집합'은 '트리'로 치환될 수 있다.
서로소 집합 자료구조
서로소 집합은 연결리스트로 구현한다.
프로퍼티
Node.data : 노드의 값이다
Node.parent : 부모 노드이다
Node.rank : 루트로부터 떨어진 길이를 의미한다. 0이면 루트노드이다.
메서드
DisjointSet.find() : 해당 노드의 부모 노드를 재귀적으로 찾는다.
DisjointSet.union() : 두 노드의 루트 노드가 다른 경우, 더 작은 루트 노드로 합친다. (합쳐지는 루트노드는 rank가 1이 증가하여 더이상 루트노드가 아니게 된다.)
코테에서 활용하기
서로소 집합 구현하기
일반적인 코테에서는 배열의 길이를 확인할 수 있기 때문에 링크드 리스트를 활용할 필요가 없다.
따라서 아래와 같이 노드의 부모를 저장하는 리스트만 하나 추가해주면 된다.
const rootArray = Array.from({ length: n }, (e, i) => i);
-
루트 노드의 조건은 '나의 value와 나의 index가 같은 경우'이다. 따라서 위의 rootArray는 모든 노드가 자기 자신을 루트로 갖고 있는 상황이다.
-
같은 Set의 조건은 '나의 루트 노드와 연결되는 노드의 루트 노드가 같은 경우' 이다.
find 구현하기
루트 노드를 찾는 find를 구현해보자.
루트 노드는 '부모 노드를 재귀적으로 호출'하여 찾는다.
재귀의 탈출 조건은 '나의 value와 나의 index가 같은 경우'이다. 해당 노드를 루트노드로 하여 rootArray를 갱신해준다.
function findParent(index) {
if (rootArray[index] === index) {
return index;
}
return findParent(rootArray[index]);
}
union 구현하기
union은
- link로 연결된 두 요소를 선정한다.
- 두 요소에 대해 findParent를 시행한다.
- 두 요소의 부모 요소가 다르다면 하나로 통일시킨다.
만일 다음과 같이 간선 리스트가 들어오는 경우 아래와 같은 결과가 나올 수 있다.
[(0, 1), (3, 4), (3, 5), (0, 2), (1, 5)]
[0, 0, 0, 5, 3, 1]
union by rank
위의 예시는 매우 비대칭적이다.
union by rank는 깊이, 즉 'rank'라는 변수를 추가한다. rank는 루트 노드로부터 떨어진 거리를 의미한다. 부모 노드의 rank를 비교하여 rank가 더 작은 쪽으로 통합하여 연결한다.
[(0, 1), (3, 4), (3, 5), (0, 2), (1, 5)]
여기서 마지막 (1, 5)를 합칠때를 보자
5로 통합되는 예시이다. 기존보다 depth가 1 줄어드는 것을 볼 수 있다.
경로 압축
function findParent(index) {
if (rootArray[index] === index) {
return index;
}
return findParent(rootArray[index]);
}
기존 예제에서 (4, 6), (4, 7)을 마지막에 추가한다고 해보자.
[(0, 1), (3, 4), (3, 5), (0, 2), (1, 5), (4, 6), (4, 7)]
4번에서 하나씩 거슬러 올라가며 8번을 탐색한다.
이때 아래와 같이 rootArray 배열의 값을 변경하는 부수 효과를 줘보자
function findParent(index) {
if (rootArray[index] === index) {
return index;
}
return (rootArray[index] = findParent(rootArray[index]));
}
(4,6) 링크를 추가할 때에, 4번 노드외 3번 노드의 root가 업데이트 되면서 0과 연결된다.
이에 따라 (4, 7) 링크를 추가할 때에는 단 2번 만에 루트 노드와 연결될 수 있게 된다.
경로 압축과 자료형의 관계
지금까지 위의 예시는 간선 리스트가 들어오기 때문에 이와 같은 비대칭 문제가 발생한 예시였다.
만일 코딩테스트에서 인접 행렬이나 인접 리스트가 들어오는 경우, 혹은 간선 리스트를 인접 리스트나 인접 행렬로 변환한 후 풀이하는 경우에는 자연스럽게 가장 작은 인덱스부터 탐색하게 되고, 이에 따라 자연스럽게 경로압축이 이루어진다.
또한 간선 리스트를 이용해 풀이할 때에도 간선 리스트를 미리 정렬하면 역시나 자연스럽게 경로 압축이 이루어진다. 아래는 간선 내부를 먼저 정렬하고, 이후에 전체 간선을 정렬하는 예시이다.
const edges = [
[1, 2],
[4, 2],
[0, 2],
];
edges.forEach(edge => {
if (edge[0] > edge[1]) {
edge.reverse();
}
});
edges.sort((a, b) => {
if (a[0] !== b[0]) {
return a[0] - b[0];
}
return a[1] - b[1];
});
//[[0,2],[1,2],[2,4]]
암튼간에, 인접행렬을 인풋으로 주는 네트워크 문제를 풀어보자
네트워크 문제
- 자기 자신을 값으로 받는 parentArray 초기화한다.
const parentArray = Array.from({length:n}, (e,i)=>i);
- find 함수를 선언한다.
인접행렬의 앞에서 부터 탐색할 것이므로 별도의 경로압축은 하지 않는다.
function findParent(index) {
if(parentArray[index] === index) {
return index;
}
return findParent(parentArray[index]);
}
- 2중 for문으로 탐색하며 union을 수행한다.
for(let i=0; i<n; i++) {
for(let j=i+1; j<n; j++) {
와 같은 형태의 이중 for문을 활용하면 전체 행렬의 절반만 탐색한다. 또한 i보다 j가 항상 더 크므로 비교 연산을 생락할 수 있다.
for(let i=0; i<n; i++) {
for(let j=i+1; j<n; j++) {
if(computers[i][j] === 1) {
const root1 = findParent(i);
const root2 = findParent(j);
if(root1 !== root2) {
parentArray[root2] = root1;
}
}
}
}
- 해당 작업을 수행하고 나면 parentArray에 통합되지 않은 루트가 존재할 수 있다. 아래의 연산을 수행하면 루트로 통합시킬 수 있으나, 비용이 큰 연산이다. 본 문제에서는 루트의 갯수만 구하면 되기에 불필요한 연산이다.
const roodArray = parentArray.map((r) => findParent(r)
최종적으로 union-find를 수행하여 루트의 갯수를 구하는 코드는 아래와 같다.
n = 10;
computers = [
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 0, 0, 0, 0, 1, 0],
[0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 1, 0, 1],
[0, 0, 1, 0, 0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1],
];
function solution(n, computers) {
let answer = 0;
const parentArray = Array.from({ length: n }, (e, i) => i);
function findParent(index) {
if (parentArray[index] === index) {
return index;
}
return findParent(parentArray[index]);
}
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (computers[i][j] === 1) {
const root1 = findParent(i);
const root2 = findParent(j);
if (root1 !== root2) {
parentArray[root2] = root1;
}
}
}
}
// console.log(parentArray); // [0, 0, 2, 2, 4, 4, 2, 6, 2, 6]
//루트 인덱스의 갯수를 반환한다.
parentArray.forEach((e, i) => {
answer += e === i;
});
return answer;
}
Test 1 〉 통과 (0.11ms, 33.6MB)
Test 2 〉 통과 (0.14ms, 33.4MB)
Test 3 〉 통과 (0.22ms, 33.6MB)
Test 4 〉 통과 (0.20ms, 33.5MB)
Test 5 〉 통과 (0.13ms, 33.5MB)
Test 6 〉 통과 (0.28ms, 33.4MB)
Test 7 〉 통과 (0.22ms, 33.4MB)
Test 8 〉 통과 (0.26ms, 33.5MB)
Test 9 〉 통과 (0.40ms, 33.5MB)
Test 10 〉 통과 (0.23ms, 33.5MB)
Test 11 〉 통과 (0.46ms, 33.7MB)
Test 12 〉 통과 (0.64ms, 33.7MB)
Test 13 〉 통과 (0.28ms, 33.5MB)
DFS 끼얹기
union 연산을 이중for문이 아닌 dfs로 진행할 수 있다.
이 경우 하나의 루트 인덱스로부터 출발하여, 해당 루트 인덱스에 연결된 모든 노드를 탐색하면서 루트 인덱스를 통합한다.
때문에, 루트가 3개라면, 최초로 dfs를 호출하는 경우도 3번이다.
한편 dfs로 한 depth씩 들어가기 때문에 경로 통합이 진행되며, dfs내부에서 for (let i = 0; i < n; i++)를 통해 모든 노드를 탐색하기에 parentArray가 rootNode로 모두 통합되는 특징이 있다. (만일 for (let i = node+1; i < n; i++)로 진행하면 통합되진 않는다. 이 경우는 위에서 for (let j = i + 1; j < n; j++)를 사용한 것과 같은 원리이다.)
function solution(n, computers) {
let answer = 0;
const rootArray = Array.from({ length: n }, (e, i) => i);
function findParent(index) {
if (roodArray[index] === index) {
return index;
}
rootArray[index] = findParent(rootArray[index]);
return rootArray[index];
}
function dfs(node) {
for (let i = 0; i < n; i++) {
if (computers[node][i] === 1) {
const root1 = findParent(node);
const root2 = findParent(i);
if (root1 !== root2) {
rootArray[root2] = root1;
dfs(i);
}
}
}
}
for (let i = 0; i < n; i++) {
if (rootArray[i] === i) {
dfs(i);
answer++;
}
}
//console.log(parentArray); //[0, 0, 2, 2, 4, 4, 2, 2, 2, 2]
return answer;
}
Test 1 〉 통과 (0.35ms, 33.6MB)
Test 2 〉 통과 (0.18ms, 33.6MB)
Test 3 〉 통과 (0.24ms, 33.4MB)
Test 4 〉 통과 (0.21ms, 33.5MB)
Test 5 〉 통과 (0.10ms, 33.5MB)
Test 6 〉 통과 (0.31ms, 33.6MB)
Test 7 〉 통과 (0.20ms, 33.4MB)
Test 8 〉 통과 (0.28ms, 33.5MB)
Test 9 〉 통과 (0.24ms, 33.5MB)
Test 10 〉 통과 (0.25ms, 33.5MB)
Test 11 〉 통과 (0.68ms, 33.7MB)
Test 12 〉 통과 (0.51ms, 33.7MB)
Test 13 〉 통과 (0.53ms, 33.5MB)
앞서 말한 dfs 내부의 for문을 수정하여 answer를 도출한 결과이다.
function solution(n, computers) {
let answer = 0;
const parentArray = Array.from({ length: n }, (e, i) => i);
function findParent(index) {
if (parentArray[index] === index) {
return index;
}
parentArray[index] = findParent(parentArray[index]);
return parentArray[index];
}
function dfs(node) {
for (let i = node + 1; i < n; i++) {
if (computers[node][i] === 1) {
const root1 = findParent(node);
const root2 = findParent(i);
if (root1 !== root2) {
parentArray[root2] = root1;
dfs(i);
}
}
}
}
for (let i = 0; i < n; i++) {
if (parentArray[i] === i) {
dfs(i);
}
}
//console.log(parentArray); //[0, 0, 6, 2, 4, 4, 6, 6, 2, 2]
parentArray.forEach((e, i) => {
answer += e === i;
});
return answer;
}
Test 1 〉 통과 (0.22ms, 33.6MB)
Test 2 〉 통과 (0.11ms, 33.5MB)
Test 3 〉 통과 (0.35ms, 33.5MB)
Test 4 〉 통과 (0.22ms, 33.6MB)
Test 5 〉 통과 (0.10ms, 33.4MB)
Test 6 〉 통과 (0.29ms, 33.4MB)
Test 7 〉 통과 (0.21ms, 33.6MB)
Test 8 〉 통과 (0.26ms, 33.6MB)
Test 9 〉 통과 (0.24ms, 33.5MB)
Test 10 〉 통과 (0.24ms, 33.4MB)
Test 11 〉 통과 (0.45ms, 33.8MB)
Test 12 〉 통과 (0.38ms, 33.7MB)
Test 13 〉 통과 (0.30ms, 33.5MB)
- 연산 결과를 보면 parrentArray를 root로 통합하지 않는 경우에 연산 속도가 훨씬 개선된다.
- 이중 반복문을 이용해 구현하는 것보다 dfs로 구현하는 편이 자료양이 많을 때에 유리하다.
- 이중 반복문이든 dfs든 간에 중요한 것은 '간선 리스트'를 입력받는대로 풀지 않는 것이다. '간선 리스트'를 적절히 정렬하거나 인접행렬 등으로 변환하고서 union-find를 하면 최적화가 잘 되어서 잘 풀린다.