유니온파인드

안녕하세요, 인프런 AI 인턴입니다.

유니온 파인드(Union-Find) 혹은 합집합-찾기 알고리즘은 집합을 효율적으로 관리하기 위한 자료구조로, 각 원소가 소속된 집합을 빠르게 찾고 두 집합을 합치는 연산을 거의 상수 시간에 수행할 수 있습니다. 이 데이터 구조는 주로 그래프의 연결성을 관리하고, 최적 알고리즘은 경로 압축(Path Compression)과 랭크 기반 합병(Rank Union)을 사용합니다.

질문 주신 내용처럼 최적화한 유니온 함수가 의도한 결과를 가져오지 않을 수 있는데, 다음과 같은 점을 확인해 보십시오:

경로 압축: find 함수에서 경로 압축을 사용하고 있는지 확인하세요. 경로 압축은 해당 노드가 속한 모든 경로의 부모를 최상위 부모로 바로 연결하여 쿼리의 시간을 줄여줍니다.

   def find(parent, x):
       if parent[x] != x:
           parent[x] = find(parent, parent[x])
       return parent[x]

랭크 기반 합병: union 과정에서는 두 집합의 랭크를 비교하여 작은 트리를 큰 트리 아래에 연결하는 방식으로 높이를 줄여야 합니다.

   def union(parent, rank, x, y):
       rootX = find(parent, x)
       rootY = find(parent, y)
       if rootX != rootY:
           if rank[rootX] > rank[rootY]:
               parent[rootY] = rootX
           elif rank[rootX] < rank[rootY]:
               parent[rootX] = rootY
           else:
               parent[rootY] = rootX
               rank[rootX] += 1

초기화 문제: 모든 노드의 부모가 자기 자신을 가리키도록 정확히 초기화되었는지 확인하세요.

위의 각 부분은 상당히 중요하며 최적화 과정 중에서 작은 코드 오류로도 원하는 결과가 나오지 않을 수 있습니다. 관련된 보다 자세한 설명은 다음 링크에서 확인하실 수 있습니다:

유니온 파인드 최적화 문제 해결

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변