Union Find에서 Union 메서드에 대한 생각 정리

이번 주차에서는 그래프에 대해서 공부를 하고 있다.

백준 문제를 풀던 와중에 최소 스패닝 트리 라는 것이 나왔고 크루스칼 알고리즘으로 문제를 풀 수 있었다.

크루스칼 알고리즘으로 문제를 풀기 위해서는 Union Find 메서드들에 관해서 알아야 한다.

그래서 Union Find 메서드들에 대해서 설명을 한번 듣고 나서 스스로 코드를 짜면서 정리를 했다.

그리고 나서 내가 짠 Union Find 메서드로 문제를 푸는데 계속해서 틀렸다고 나왔다.

그러다가 반례를 찾았고 디버깅을 해보니 내가 짠 코드에는 큰 문제가 하나 있었다.

내가 처음에 짠 코드

def union_parent(parents, ele1, ele2):
    ele1_parent = find_parent(parents, ele1)
    ele2_parent = find_parent(parents, ele2)

    if ele1_parent < ele2_parent:
        parents[ele2] = ele1_parent
    else:
        parents[ele1] = ele2_parent

정답 코드

def union_parent(parents, ele1, ele2):
    ele1_parent = find_parent(parents, ele1)
    ele2_parent = find_parent(parents, ele2)

    if ele1_parent < ele2_parent:
        parents[ele2_parent] = ele1_parent
    else:
        parents[ele1_parent] = ele2_parent

달라진 부분은 해당 부분이다.

if ele1_parent < ele2_parent:
    parents[ele2_parent] = ele1_parent
else:
    parents[ele1_parent] = ele2_parent

---

부모의 부모를 업데이트 해줘야 한다

내가 처음에 생각한 것은 내가 원하는 노드의 부모를 찾았으면 그 노드의 부모만 바로 업데이트를 해주면 된다고 생각했는데 정확하게 이 부분이 틀렸다. (내가 처음에 내 생각대로 코드를 짜면서 이렇게 하는게 더 빠른거 같은데 왜 이렇게 안하지? 라고 생각했다... 내 생각은 허술한 부분이 있었다.)

내 방식대로 코드를 구현하게 되면 단순하게 내가 원하는 노드의 부모만 바뀌고 그 노드가 이루고 있던 Union들의 내용은 업데이트 되지 않는다. => 내가 원하는 노드가 자기의 Union을 벗어나 다른 부모의 Union으로 들어간다고 볼 수 있다. (잘 못 되었다.)

부모의 부모를 업데이트 해줘야 해당 부모를 참조하고 있는 모든 노드들의 부모가 업데이트 되고 해당 노드의 Union이 다른 Union이랑 합쳐진다. ※진정한 Union이 된다.