[프로그래머스] 네트워크(feat. Union-Find)🚨

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

아주아주 풀어보는 게 다행인 문제였다.

 

이 문제를 보자마자 Union-Find 문제라는 점은 알아차렸고, 최적화도 적용했다.

하지만 몇 개의 테스트 케이스가 자꾸 통과하지 못해서 문제가 이상하나? 라고 생각했으나, 내가 이상한 거였다.

 

Testcase #7.

테스트 케이스7번을 통과하지 못한 이유는 union 함수를 잘못 짰다.

 

void _union(int x, int y) {
    int parent_x = _find(x);
    int parent_y = _find(y);
    
    if(parent_x == parent_y) return;
    // union은 부모끼리 해야한다!!
    if(parent_x < parent_y) {
        parent[parent_y] = parent_x;
    }
    else {
        parent[parent_x] = parent_y;
    }
}

parent(root) 값을 교체할 때, 상대의 루트 값 자체를 바꿔야 한다.

즉 만약 a의 자식을 b의 자식으로 만들 때, a가 아니라 a의 parent 값을 b로 만들어야 한다.

 

그래야 트리의 길이가 길어지지 않고, 정상적으로 의도한대로 루트인 parent를 찾아낼 수 있다.

Testcase #9.

위의 코드를 수정하고도 여전히 9번 테스트케이스를 통과하지 못했다.

왜 그럴까?

 

바로 자동으로 parent가 루트를 가리키는 것이 아니라, find 함수를 호출해야 경로가 축소된다.

그래서 마지막에 루트를 찾기 위해 find함수를 호출해 최적화작업을 마무리해야 한다.

for(int i = 0;i < n;i++) {
    s.insert(_find(parent[i]));
}