Union-Find 유니온 파인드

2020/11/06 - [문제풀이/자바] - [백준 1976] 여행 가자 (자바)

[백준 1976] 여행 가자 (자바)

위에서 유니온 파인드에 대한 설명을 잠깐 했습니다.

하지만 제가 이 개념을 이해하고 왜 부모 값(대푯값)을 자꾸 건드리는지 이해하는데 많은 시간이 걸렸습니다.

 

아래 예시를 통해 이해를 하길 바랍니다.

위의 형태로 각 노드를 연결했고 밑은 그 출력문입니다.

 

초기값은 0~5였지만, union 후에 001111로 바뀐 것을 볼 수 있습니다. 이것은 의도한 값입니다.

그 후 3의 값을 parent와 find를 이용하여 호출해봤습니다.

그 값이 서로 다른 것을 볼 수 있습니다.

이 때 find를 호출하며 최적화가 됐기 때문에 다시 3의 parent와 find를 호출했지만, 같은 값인 0이 나옵니다.

그리고 전체 parent 배열을 출력해보니 3의 값이 바뀐 것을 볼 수 있습니다.

 

이런 이유 때문에 제 코드를 응용한 유니온 파인드는 parent의 값을 읽는 것을 지양하고 find를 이용하는 것을 지향해야 합니다.

만약 최적화가 되지 않는다면 0-1-2-3-4-.................-n개가 일렬로 연결된다면 n의 부모 값을 읽을 때 O(n)의 시간 복잡도를 가지게 됩니다.

하지만 최적화를 했을 때는 O(1)로 처리가 가능합니다.

 

아래는 예시에서 이용된 코드입니다.