유니온 파인드 (2) 썸네일형 리스트형 백준 16562번: 친구비 C++코드(Union Find, 유니온 파인드, 분리 집합) #include using namespace std; int friendCost[10001]; int friendCostMin[10001] = {0,}; int parents[10001]; int find(int n){ if(parents[n-1] == n){ return n; }else{ int temp = find(parents[n-1]); return temp; } } void Union(int a, int b){ a = find(a); b = find(b); if(a < b){ parents[b-1] = a; }else{ parents[a-1] = b; } } void Union2(int n){ int now = n; n = find(n); parents[now-1] = n; } int main(.. Union-Find(유니온 파인드)에 대해 알아보고 구현하기 Union-Find? 유니온 파인드. 그대로 해석하면 union은 조합, find는 찾다로 해석이 가능하다. 실제로 이 알고리즘은 두 연산 find와 union를 사용한다. 여러 개의 노드가 있다고 가정했을 때 2개의 노드를 union을 통해 합치는 것도 가능하고, find를 통해 해당 노드의 부모노드를 찾는 것 또한 가능하다. 전체적인 구현 방법 노드들의 부모를 나타낼 배열을 선언해줘야한다. 예를 들어 트리를 다룬다고 했을 때 직접적으로 간선을 옮겨주는 식으로 할 수 없는가? 라는 생각을 가질 수 있으나, 가능은 하나 노드들의 부모가 하나로 통일됬는 지 검사하는 등의 연산이 필요할 경우, 시간복잡도가 난해해지므로 O(n)으로 끝낼 수 있게 노드들의 부모를 나타낼 배열을 선언해줘야한다. 부모노드가 없을 .. 이전 1 다음
