Union-Find(Disjoint-Set) 에 대해, + BOJ 4195

안녕하세요 원재입니다 ^ㅡ^ 이번에는 알고리즘에서 주로 쓰이는 (특히 그래프 알고리즘) Union-Find 에 대해서 알아보려고 합니다! Union-Find 는? Union-Find 의 가벼운 첫 인상을 알려드리자면, Union-Find 는 우리 조상님 찾기 라고 볼 수 있습니다! 조상님이라고 부르세요 위와 같은 그래프가 있다고 생각해 봅시다. 루트 노드는 1 과 5 가 되겠죠? 3,4 를 자식으로 가지는 1번 트리와, 6, 2를 자식으로 가지는 5번 트리가 존재한다고 생각하겠습니다. 그렇다면 우리는 Union-Find 를 통해 4의 조상님은 1이에요! 라는 것을 Find 할 수 있습니다. 그렇다면 Union 은 어떨때 사용할까요? 바로 족보 구매 입니다. 족보입니다 만약 위와 같은 노드에서 5번 노드가..