Lee 코딩 Lee 코딩

= Disjoint-Set 서로소 집합 알고리즘이라고도 불림. 그래프에서 여러 개의 노드 중 두 개의 노드를 선택해서 이 노드들이 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. - find : 노드의 부모가 같은지 확인하여 현재 같은 집합에 속하는지 확인하는 것 - union : 두 노드가 각각 포함되어 있는 집합을 합치는 것 1. 처음에 모든 노드들이 연결되어 있지 않을 때 -> 자기 자신이 부모 i 0 1 2 3 4 5 parent[i] 0 1 2 3 4 5 2. 1과 3, 2와 5가 각각 연결되어 있을 때 i 0 1 2 3 4 5 parent[i] 0 1 2 1 4 2 1과 3의 부모를 합쳐주고, 2와 5의 부모를 합쳐 준다(Union) 이 때는 더 작은 값으로 합쳐준다 3. 1-2-3처럼 연..