유니온-파인드 알고리즘

최근 유니온 파인드 알고리즘을 푸는데 개념은 이해했고 알고 있지만 백준 문제에 적용해서 풀려고 하니 어려워 제대로 아는 것이 아니다라고 생각해서 이렇게 정리하려고 한다.

유니온 파인드?

유니온-파인드는 그래프에서 두 노드가 같은 집합에 속하는지 판별하는 알고리즘이다.

유니온 연산은 두 노드를 같은 집합에 있도록 합치는 연산이고 find 연산은 해당 노드의 루트노드를 찾는 연산이다.

둘을 합쳐 유니온-파인드라 한다.

결국 두 집합이 있을 때 2번 노드와 4번 노드가 같은 집합에 있는지 알아내는 방법이다.

그림에서는 2번 노드의 루트 노드는 0번 노드이고 4번 노드의 루트 노드 또한 0번 노드임을 쉽게 확인할 수 있다.

여기서 답이 나왔다.

두 노드를 입력했을 때 두 노드의 루트 노드를 각각 파인드 연산으로 찾았을 때 같으면 두 노드는 같은 집합에 있는 것이고 루트가 다르면 서로 다른 집합에 있다.

유니온-파인드 알고리즘으로 서로 다른 두 노드가 같은 집합에 있는지 다른 집합에 있는지 확인할 수 있다. 또 필요에 따라 쉽게 두 집합을 확인할 수 있다.