글 읽기 - 1717 집합의 표현 (Union-find) 질문

quf9484 2년 전 0

안녕하세요,

항상 친절하게 답변해주시는 고수님들 :)

오늘도 질문이 있습니다. 아래는 union-find 제 코드입니다.

union 함수에서 부모 노드를 할당해줄때, 항상 최상위 부모 노드(find 값)을 할당 해주어야 하는 이유가 있나요?

첫 번째 union 함수 처럼 할당을 하여도, find 함수는 재귀적으로 호출하기 때문에 최상위 부모를 찾아서 비교 할 수 있는 것 아닌가요?

그래서 두 번째 union 함수는 성능 향상을 위한 목적이지 첫 번째 함수도 정답이라고 생각하는데 틀렸다고 나옵니다.

감사합니다!

def union(a, b):
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        
# ---

def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def find(n):
    if parent[n] == n:
        return n
    parent[n] = find(parent[n])
    return parent[n]

yijw0930 2년 전 0

parent[a]=b에서 b는 최상위 부모 노드일 필요가 없지만 a는 최상위 부모 노드여야만 합니다.

위 식의 의도는 a와 연결된 모든 노드 c에 대하여 find(c)=find(b)가 되는 것인데, 만일 a가 최상위 노드가 아니라면 a의 최상위 노드에 find 연산을 한 값이 여전히 그 자신이 되기 때문입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1717 집합의 표현 (Union-find) 질문

quf9484 2년 전 0

yijw0930 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말