PHP에서의 분리된 집합(Union-Find 알고리즘)
게시됨: 2025년 2월 16일 오후 12시 25분 57초 UTC
이 문서에서는 최소 신장 트리 알고리즘의 Union-Find에 일반적으로 사용되는 Disjoint Set 데이터 구조의 PHP 구현을 소개합니다.
Disjoint Set (Union-Find Algorithm) in PHP
Disjoint Set(일반적으로 Union-Find, Disjoint Set Union에 사용됨)은 요소를 분리된(겹치지 않는) 세트로 분할하는 데 사용되는 데이터 구조입니다. 두 가지 주요 작업을 효율적으로 지원합니다.
- 찾기 : 요소가 어느 집합에 속하는지 판별합니다.
- 합집합 : 두 개의 집합을 합칩니다.
이 구조는 크루스칼 알고리즘과 같은 최소 신장 트리 알고리즘에 특히 유용합니다.
무작위 미로를 생성하는 데 사용되는 Kruskal 알고리즘 구현이 있는데, 이는 Disjoint Set의 아래 PHP 구현에 의존하여 효율적으로 세트를 병합합니다. 관심이 있다면 여기에서 실제로 볼 수 있습니다: 크루스칼 알고리즘 미로 생성기
어쨌든, 이게 제가 Disjoint Set을 PHP로 구현한 것입니다.
{
private $parent = [];
private $rank = [];
public function __construct($size)
{
for ($i = 0; $i < $size; $i++)
{
$this->parent[$i] = $i;
$this->rank[$i] = 0;
}
}
public function find($x)
{
if ($this->parent[$x] != $x)
{
$this->parent[$x] = $this->find($this->parent[$x]);
}
return $this->parent[$x];
}
public function union($x, $y)
{
$rootX = $this->find($x);
$rootY = $this->find($y);
if ($rootX != $rootY)
{
if ($this->rank[$rootX] > $this->rank[$rootY])
{
$this->parent[$rootY] = $rootX;
}
elseif ($this->rank[$rootX] < $this->rank[$rootY])
{
$this->parent[$rootX] = $rootY;
}
else
{
$this->parent[$rootY] = $rootX;
$this->rank[$rootX]++;
}
}
}
}
재미 삼아 미로를 만드는 것 외에도, Disjoint Set 데이터 구조는 실제 상황에도 확실히 사용할 수 있습니다.
예를 들어, 사용자에게 새로운 친구를 추천하고 싶어하는 소셜 네트워크를 상상해 보세요. 그리고 이미 이러한 친구 관계가 있는 사람이 6명 있다고 가정해 봅시다.
- 1과 2는 친구입니다.
- 2와 3은 친구입니다.
- 4와 5는 친구입니다.
- 6은 친구가 없습니다.
이러한 개별 그룹에 Union-Find 알고리즘을 적용하면 다음과 같은 결과를 얻을 수 있습니다.
- 1, 2, 3이 한 그룹에 속함.
- 두 번째 그룹은 4와 5입니다.
- 세 번째 그룹은 6명.
이를 바탕으로, 1과 3은 사람 2와 공통점이 있으므로 친구가 되는 것이 합리적입니다.
물론, 이와 같은 작은 예에서는 여러분도 쉽게 이 사실을 알아낼 수 있겠지만, 이 알고리즘의 효율성 덕분에 수십억 명의 사람들과 친구 그룹으로 확장하는 것이 가능합니다.