[Algorithm] Union-Find 알고리즘 (JAVA 구현)

-Union Find 알고리즘이란? 서로소 집합 알고리즘과 같은 개념으로 여러 개의 노드가 존재하는 그래프에서 두 노드가 연결되어있는지 판별하는 알고리즘이다. 구현에 필요한 자료구조로는 1) 모든 정점들의 부모 정점을 표현하기 위한 배열이 필요하다. 다음과 같이 6개의 독립적인 노드가 존재한다고 할 때 배열을 이용해서 원소에 해당 노드의 부모 노드를 표시하게 된다. 현재는 모두 독립된 노드이기 때문에 자기 자신을 부모로 삼는다고 할 수 있다. 1 2 3 4 5 6 1 2 3 4 5 6 이와 같은 상태에서 만약 1번 정점과 2번 정점이 연결을 수행하게 되면 두 정점을 합치는 Union작업이 수행되게 되는데, 이 과정을 거치고 나면 아래와 같이 2번 정점의 원소를 부모 정점인 1로 바꿔주게 된다. 이 과정에..