서로소 집합1 Union-Find의 최적화 과정 Union-Find는 말 그대로 임의의 그룹과 그룹을 묶고(Union) 두 노드가 같은 그룹인지 확인(Find) 하는 알고리즘이다. 하나씩 따라 해 보면서 어떻게 구현하고, 최적화시키는지 확인해보자. Union Find는 그룹을 하나의 트리로 표현한다. 이렇게 하면 두 노드가 같은 그룹인지 확인할 때 단순히 root 노드가 같은지만 확인하면 되기 때문에 간단해진다. void unionGroup(int x, int y) { int rootX = findRoot(x); int rootY = findRoot(y); parent[rootX] = rootY; } bool isSameGroup(int x, int y) { return findRoot(x) == findRoot(y); } 첫 번째 함수는 x와 y를 .. 2019. 10. 16. 이전 1 다음
