CS/알고리즘 (9) 썸네일형 리스트형 [C++] 합집합 찾기(Union-Find) 합집합 찾기는 그래프의 연결 유무를 판별할 때 쓰이는 알고리즘이다. 세 가지 함수만 구현하면 된다. 1. getParent - 부모 값 반환 2. unionParent - 부모 노드 합치기 3. findParent - 같은 부모 노드를 가지는지 확인(연결여부 판별) 먼저 노드 사이의 관계를 파악하기 위해 Parent라는 배열을 만든다. 노드의 개수만큼 크기 설정을 해주면 된다. 예를 들어 노드의 개수가 다섯 개면 아래와 같이 초기화해준다. 노드 사이의 연결관계는 Parent의 원소값으로 판단한다. 일반적으로 parent는 원소값이 작은 값을 기준으로 한다. 만약 1과 5를 연결하면 아래와 같다. 이제 Parent[5] = 1로 바뀐 과정을 살펴보자. 가장 기초가 되는 getParent 코드는 아래.. 이전 1 2 다음
