그래프와 관련된 알고리즘 문제를 푸려면 꼭 알고 있어야하는 알고리즘이 있습니다.
바로 Union-Find
알고리즘이죠.
이 알고리즘을 토대로 Kruskal
같은 확장된 알고리즘들을 구현하게 되는데요,
그렇기 때문에 더더욱 Union-Find
알고리즘에 대해 정확히 알고 있을 필요가 있습니다.
Union-Find
알고리즘을 살펴보기 전에, 먼저 그래프 관련 용어부터 간단하게 짚고 넘어갈게요.
노드(Node) : 그래프의 각 정점
간선(Edge) : 그래프의 각 정점을 잇는 선
이제 알고리즘에 대해 살펴보겠습니다.
Union-Find
알고리즘이 해결하고자 하는 문제가 무엇인지부터 알아보죠.
위의 그림과 같이 그래프가 주어졌을 때, 그래프 내의 임의의 두 정점이 한 그래프에 속해있는지 여부를 알아내야 하는 상황에 놓여있다고 생각해봅시다.
예컨대 정점 1
과 정점 3
는 한 그래프 내에 속해있죠. 이 사실을 컴퓨터가 어떻게 판단하도록 만들 수 있을까요?
뭔가 아이디어가 복잡할 것도 같지만,
생각보다 단순합니다.
아이디어의 핵심은 다음과 같아요.
- 각 정점의 부모가 누구인지를 표현하는 배열을 선언한다.
- 배열의 index 가 곧 node 번호다.
- 배열의 초깃값은 각 node 들의 번호(자기자신)다.
- 그래프의 연결 정보를 보고 배열 값을 업데이트 한다.
- 두 노드를 연결할 때, 항상 낮은 번호의 노드를 부모로하여 연결한다. 이 과정을
Union
이라 표현한다. (ex.노드 1
과노드 2
를 Union 하면노드 1
이노드 2
의 부모가 된다.- 두 노드를 연결할 때, 한 노드의 부모를 찾는 과정은 재귀적으로 진행된다. (ex. 위 단락의 그래프 예시에서
노드 3
의 부모는노드 2
지만,노드 2
의 부모는노드 1
이므로노드 3
의 부모는노드 1
로 기록한다.
이제 이 아이디어를 위의 예시 그래프 상황에 적용시켜 볼게요.
우선 위와 같이 배열을 초기화 해둡니다.
앞서 말씀드린대로 배열의 index 는 각 노드의 번호를 뜻하며 배열[n]
의 값은 노드 n
의 부모 노드를 나타냅니다.
노드 번호 0번은 사용하지 않을 예정이므로 비워둡니다.
그래프의 상태를 다시 살펴보겠습니다.
간선은 총 5개네요. 차례로 한 번 연결시켜 보도록 하겠습니다.
우선 첫 번째로 노드 1
과 노드 2
를 연결시킨 후의 배열 상태를 관찰해보겠습니다.
노드 2
의 부모가 노드 1
로 변경된 것을 확인할 수 있습니다.
다음으로 노드 2
와 노드 3
을 연결해 볼게요.
노드 3
의 부모는 노드 2
이지만, 노드 2
의 부모가 노드 1
이므로 노드 3의
부모는 노드 1
이라고 기록해 주었습니다.
나머지 간선들도 연결하면 최종 배열의 상태는 다음과 같아집니다.
이제 이 로직을 구현해보도록 할까요?
우선 각 노드의 부모를 계산하는 함수부터 짜보도록 할게요.
// 각 노드의 부모가 누군지 계산하는 함수
function findParent(parentOf, node) {
if (parentOf[node] === node) {
// 자기 자신이 부모라면 그대로 return
return node
}
// 자기 자신이 부모가 아니라면 재귀적으로 부모를 찾아감.
// 부모를 찾았다면 해당 node 의 부모를 업데이트 해줌.
return parentOf[node] = findParent(parentOf, parentOf[node])
}
다음으로 두 노드의 부모 노드들을 연결하는 함수를 작성해볼게요
function unionParent(parentOf, nodeA, nodeB) {
const parentOfNodeA = findParent(parentOf, nodeA)
const parentOfNodeB = findParent(parentOf, nodeB)
if (parentOfNodeA < parentOfNodeB) {
// Node A 의 부모가 더 작은 값이라면
// Node B 의 부모의 부모를 Node A의 부모로 교체한다
parentOf[parentOfNodeB] = parentOfNodeA
} else {
parentOf[parentOfNodeA] = parentOfNodeB
}
}
이 함수는 언뜻 봐서는 이해가 안될 수 있으니 예시를 들어 보충 설명해볼게요.
위 그림처럼 노드 3
과 노드 5
를 unionParent
함수의 인자로 줘 보겠습니다.
unionParent(parentOf, 3, 5)
이 함수의 호출은 뭘 의미할까요?
바로,
노드 3의 부모(노드 1)
와노드 5의 부모(노드 4)
를 연결해준다.
즉,노드 3
이 속한 그래프와노드 5
가 속한 그래프를 연결해준다.
입니다.
함수의 실행 결과는 다음과 같아질거에요.
마지막으로, 두 노드의 부모가 같은지(같은 그래프 내에 있는지)를 체크하는 함수도 짜보죠.
function isInSameGraph(parentOf, nodeA, nodeB) {
const parentOfNodeA = findParent(parentOf, nodeA)
const parentOfNodeB = findParent(parentOf, nodeB)
if (parentOfNodeA === parentOfNodeB) {
// 두 노드의 부모가 같다면 true
return true
}
// 같지 않다면 false
return false
}
이제 구현한 알고리즘을 사용해 볼 차례입니다.
우선 위와 같은 그래프 상태에서 시작을 해보겠습니다.
// 배열 초기화
const parentOf = [null] // 노드 0 번은 존재하지 않으므로 null 할당
const numNodes = 7
for (let i = 1; i <= numNodes; i++) {
parentOf.push(i)
}
// 그래프의 초기 상태를 표현
unionParent(parentOf, 1, 2)
unionParent(parentOf, 2, 3)
unionParent(parentOf, 4, 5)
unionParent(parentOf, 5, 6)
unionParent(parentOf, 6, 7)
// 노드 1과 노드 3은 같은 그래프 내에 있음
console.log(isInSameGraph(parentOf, 1, 3)) // true
// 노드 4와 노드 7은 같은 그래프 내에 있음
console.log(isInSameGraph(parentOf, 4, 7)) // true
// 두 개의 graph 연결
unionParent(parentOf, 3, 5)
// 노드 3과 노드 5는 같은 그래프 내에 있음
console.log(isInSameGraph(parentOf, 3, 5)) // true
// 최종 배열 상태 확인
console.log(parentOf) // [ null, 1, 1, 1, 1, 1, 4, 4 ]
그래프 그림을 보면서 알고리즘을 천천히 따라가 보시면 어렵지 않게 이해하실 수 있을거에요.