Beelog

문제는 위와 같습니다. 저한테는 조금 난이도가 있었던 문제였습니다. 먼저 이 문제는 Union-Find 알고리즘을 사용하였습니다. Union-Find 알고리즘은 Disjoint Set을 표현하기 위한 알고리즘인데, Disjoint Set 은 서로 중복되지 않는 부분 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조로 서로소 집합 자료구조입니다. 이 문제를 해결하기 위해 딕셔너리 타입으로 자신(key)과 연결된 대표 노드(value)를 표현하고, 새로운 조합이 들어올 때마다 각각의 대표 노드(부모 노드)를 찾아서(Find) 다른 쪽의 부모 노드로 연결(Union)해 주면서 union 과 find 를 반복하는 것입니다. 또한 이때 연결되는 노드의 수를 알아야하기 때문에 이를 표현하는 딕셔너리..