유니온

[알고리즘] 유니온과 파인드 알고리즘(union, find)

Union과 find는 집합과 관련된 연산이다. - Union : 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 연산 - find : 두 노드가 같은 집합에 속해 있는 지를 확인하는 연산 코드 상에서의 구현 방법도 어렵지 않다. 일반적으로 유니온과 파인드를 구현하기 위해 1차원 배열을 사용한다. 초기에는 아무 노드도 연결되어 있지 않기 때문에 각 노드가 대표노드가 되며 자신의 인덱스 값으로 초기화 된다. union은 두 노드의 대표노드를 일치시키는 연산이다. 이 과정에서 재귀적으로 대표노드를 찾는 과정이 포함될 수 있다. find는 자신이 속한 집합의 대표노드를 찾는 연산이다. 이 과정이 중요한 이유는 단순히 노드를 찾을 뿐만 아니라, 그래프를 정돈하고 시간 복잡도를 향상시키기 때..