[개념]

개념 : https://blog.naver.com/ndb796/221230967614

17. Union-Find(합집합 찾기)

 

# 최상위 부모를 재귀로 찾습니다.
def getParent(parent, x):
    if parent[x] == x: return x
    return getParent(parent, parent[x])

# 각 부모 노드를 합칩니다.
def unionParent(parent, x, y):
    x = getParent(parent, x)
    y = getParent(parent, y)

    # 더 작은 수를 부모로 갖습니다.
    if x < y:
        parent[y] = x
    else:
        parent[x] = y


# [확인]같은 부모 노드를 가지는지 확인합니다.
def findParent(parent, x, y):
    x = getParent(parent, x)
    y = getParent(parent, y)
    if x == y : return 1
    else: return 0



parent = [0] * 11
for i in range(1, 11):
    parent[i] = i

unionParent(parent, 1, 2)
unionParent(parent, 1, 2)
unionParent(parent, 1, 2)
unionParent(parent, 1, 2)
unionParent(parent, 1, 2)
unionParent(parent, 1, 2)
unionParent(parent, 1, 2)

print('1과 5는 연결되어 있나요?', findParent(parent, 1, 5))
unionParent(parent, 1, 5)
print('1과 5는 연결되어 있나요?', findParent(parent, 1, 5))