unionset 썸네일형 리스트형 1976 - 여행 가자 MST (Minimum Spanning Tree, 최소신장트리)를 하려면 크루스칼 알고리즘이 필요합니다. 근데 크루스칼 알고리즘을 사용하기 위해선 Union Find라는 알고리즘이 또 필요합니다. 그렇다면 차근차근 Union Find부터 알아봅시다. Union Find란 서로가 속한 집합이 같은 집합인지 파악하는 것입니다. 즉, 학교 내의 학생 2명이 같은 반인지를 확인하는 알고리즘이라 생각하면 됩니다. Union Find를 구현하기 위해 배열과 Tree를 사용할 수 있지만, 본 글에서는 배열로 다루는 Union Find를 설명할 것입니다. Union Find를 구하기 위해선 총 3개의 행위(메소드)가 필요합니다. 우선 배열을 초기화하는 init과 각자의 Root를 구하기 위한 find, 서로 같은 Ro.. 더보기 이전 1 다음