[알고리즘] Union-Find

Yoon Han·2022년 9월 18일
0

알고리즘

목록 보기
2/2
post-thumbnail

그래프와 관련된 알고리즘 문제를 푸려면 꼭 알고 있어야하는 알고리즘이 있습니다.

바로 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노드 5unionParent 함수의 인자로 줘 보겠습니다.

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 ]

그래프 그림을 보면서 알고리즘을 천천히 따라가 보시면 어렵지 않게 이해하실 수 있을거에요.


Reference

profile
챗바퀴는 도는 삶이 싫은 프론트엔드 엔지니어

0개의 댓글