Union-find

[Algorithm] 유니온 파인드 (Union-Find) 알고리즘

Union-Find Idea 유니온 파인드 알고리즘은 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘입니다. 노드를 합치는 Union 연산과 root 노드를 찾는 Find 연산으로 이루어집니다. 이러한 연산을 토대로 서로소 집합(공통 원소가 없는 두 집합) 자료 구조라 불리기도 합니다. 기차를 통해 출발지와 도착지를 정해서 이동이 가능한 지 판별하려고 합니다. 그래프를 통해 기차를 타고 서울에서 강릉으로 가는건 가능하지만 서울에서 부산으로 가는건 불가능하다는 것을 알 수 있습니다. 문제는 그래프가 복잡해지면 이러한 판단이 어려워 집니다. Union-Find 알고리즘을 이용하여 복잡한 그래프에서 두 노드가 연결되어 있는지 판별할 수 있습니다. 동작 과정 8개의 단절된 노드들이 있고, 이 노드들은 배열에..