서로소 집합(Disjoint Set)과 유니온 파인드란?
서로소 집합(Disjoint Set)과 유니온 파인드란? — #서로소집합 #DisjointSet #유니온파인드 #unionfind #개발자의도구들 AI스쿨 msa기반 java 백엔드 코...
#서로소집합 #DisjointSet #유니온파인드 #unionfind #개발자의도구들
AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다
\* 하루 1코테 도전중에 있습니다. 어떤건지 궁굼하신 분들은 여기를 눌려주세요.
왜 알아야 하는가
이전글을 통해 MST란 무엇인지에 대해 다워보았는데요. 보신분들은 MST는 Spanning Tree의 한 종류이며, Tree의 특징에 대해서도 잘 알고계시리라 생각됩니다.
Tree의 주요특징중 하나는 사이클이 없다는 겁니다. 하지만, 개념을 알고 들어가도 Tree가 Cycle인지 아닌지를 판단하는 알고리즘을 구현하기가 까다롭습니다. 저는 실제로 Cycle 판단 알고리즘을 구현하는데 꽤나 애를 먹기도 하였습니다. 이유는 효율적으로 싸이클을 찾는 방법론에 대해 몰랐기 때문이라고 생각합니다.
오늘 배울 Disjpint Set과 Union Find 알고리즘은 사이클 여부를 판단하는 좋은 알고리즘 중 하나입니다. 제가 처음부터 이 개념을 잡고 들어갔다면, 훨씬 더 빠르게 코드를 구현했었을 것 같습니다.
본격적인 MST구현 이전에 꼭 공부하고 들어가시는기를 바랍니다!
Disjoint Set
서로소 집합란?
Disjoint Set은 서로소 집합이라고 번역되는데, 이때 서로소는 두 수 사이에서의 공통된 약수가 1 밖에 없는 수를 의미합니다. 예를들어 21, 25와 같은 수를 서로소라고 합니다.
서로소 집합은 서로소의 개념을 집합에 넣은 것으로, 두 집합사이의 공통된 원소가 없는 집합의 묶음이라고 보시면 될 것 같습니다. (공집합 제외)
Disjoint Set - cycle판단에 활용되는 이유
서로소 집합란?
이를 그래프 사이클 판단에 활용되는 이유는 다음과 같은 성질이 있기 때문입니다.
어떤 수를 약수로 우선 나눠봅시다. 12의 경우 1, 2, 3, 4, 6, 12가 됩니다. 이때 12의 약수를 {1, 2, 3,4, 6, 12} 이렇게 집합으로 표현이 가능합니다. 이를 12로 향하는 하나의 길로도 볼 수 있는데요.2 -> 6 -> 12/ 3 -> 4 -> 12 이렇게 12라는 목적을 향해 가는 길로 볼 수 있겠습니다.
트리는 반드시 부모, 혹은 자식 노드가 존재합니다. 부모 노드 역시 루트노드가 아니라면 부모가 존재하는 구조입니다. 트리내에서는 단 하나의 루트노드만 존재하며 나머지 노드들은 약수처럼 루트로 향해가는 길로 볼 수 있는 것입니다.(실제로는 root에서 출발합니다, 개념적으로 이해해주세요)
만약 두 노드가 같은 집합에 속해있다면, 두 노드의 루트 노드가 같습니다. 사이클을 형성한다는 것은 보통 다시 돌아온다는 개념으로 사용됩니다. 두 개의 노드가 같은집합에 속해있다면, 트리의 경우, 결국 root로 다시 돌아오는 형태, 혹은 같은 루트를 가진 노드로 돌아오는 형태(트리는 반드시 한 방향이기 때문)가 될 수 있습니다. 이때 cycle이 발생합니다.
반면, 두 노드가 서로소 집합이라면, 서로 다른 루트 두개가 존재하기 때문에, 사이클을 형성하지 않습니다. 따라서 Disjoint Set을 활용하면, 두 노드가 같은 집합에 속해있는지, 아닌지 확인할 수 잇는 것입니다.
Disjoint Set 구현
서로소란?
| class DisjointSet: def \_\_init\_\_(self): self.parent = {} self.rank = {} def set(self, tree): self.parent = {node: node for node in tree} self.rank = {node: 0 for node in tree} |
|---|
입력으로 tree를 입력받아, 해당 tree가 사이클을 형성하는지 안하는지에 대한 여부를 판단해볼 예정입니다. 우선 tree의 모든 노드에 대하여 parent를 자기 자신으로 지정하고, rank를 모두 0으로 등록합니다.
트리는 root부터 시작하여 하나씩 추가되는 형태가 될 것 입니다.
Union Find(유니온 파인드) 알고리즘 추가
보통 DisjointSet과 함께 유니온 파인드(Union Find) 알고리즘이 사용됩니다. 이 알고리즘은 다음과 같은 큰 기능을 가지고 있습니다.
| 🔧 UNION : 서로소인 두 노드를 합하여, 하나의 집합으로 형성한다. 🔧 FIND: 노드의 부모를 찾아준다. |
|---|
이름에 걸맞게 기능들도 직관적입니다. 두 노드가 각기 다른서로소 집합에 속해있다면, UNION해주어 하나의 집합을 형성합니다. Spanning Tree를 만들며 노드를 순차적으로 방문하게 되는데, 이때 Union Find를 사용하여 이전에 방문했던(같은 집합인지) 노드를 확인할 수 있습니다.
두 집합은 root가 서로 다르기 때문에 UNION 가능
이를 위해서, FIND 메서드가 필요합니다. 서로 다른 서로소 집합의 부모를 찾아서 서로 비교해야하기 때문이죠.
Union Find(유니온 파인드) 알고리즘 구현
| class DisjointSet: def \_\_init\_\_(self): self.parent = {} self.rank = {} def set(self, nodes): self.parent = {node: node for node in nodes} self.rank = {node: 0 for node in nodes} def find(self, node): print("start find node:", node) if self.parent\[node\] != node: self.parent\[node\] = self.find(self.parent\[node\]) return self.parent\[node\] def union(self, u, v): rootU = self.find(u) rootV = self.find(v) if rootU != rootV: if self.rank\[rootU\] > self.rank\[rootV\]: self.parent\[rootV\] = rootU elif self.rank\[rootU\] < self.rank\[rootV\]: self.parent\[rootU\] = rootV else: self.parent\[rootV\] = rootU self.rank\[rootU\] += 1 return True else: return False |
|---|
graph를 처음에 집어넣어, 모든 노드에 대한 parent를 자기 자신으로 초기화 합니다. tree를 구성하고자하는 노드 쌍을 DisjointSet의 union을 통해 사이클 확인이 가능합니다. 더 자세한 내용은 Kruskal 알고리즘에서 설명하겠습니다.