프로그래머스 / Lv.3 / 네트워크 / Union-Find

 

Union-Find 사용 시 주의점에 대해 다시 생각해보는 계기가 되었기에 기록을 남겨둔다.

 

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

위 문제를 풀면서 놓치고 있던 점을 알게됐다.

유니온 파인드는 리프노드를 먼저 Find하고 그 후에 중간위치 노드를 Find하면 리프노드는 Parent값이 갱신되지 않는다.

물론 중간위치 노드를 먼저 Find한 후 리프노드를 Find하면 다 갱신되겠지만 항상 이렇지는 않으므로 마지막에 모든 Parent[]에 대해 Find를 수행해줘야 최종적으로 값이 갱신된다.

 

이게 보통 크루스칼 알고리즘에서 Union-Find를 많이 쓰다보니까 최소신장트리 특성상 간선이 V - 1개 선택되면 더는 진행할 필요가 없어서 거기서 break를 해왔었고 그래서 Parent가 최신상태로 갱신되지 않아도 거리만 맞게 계산되면 그만이었기에 생각하지 않았던 부분이다.

 

하지만 Union-Find로 부분집합이 몇개로 나누어져있는지 파악한다면 최신상태로 Parent를 업데이트해야하므로 인접배열을 모두 Union한 후 마지막에 한번 더 Find를 해줘야 한다.

아래 코드에서는 set에 넣으면서 Find해줬다.

 

정답 코드)

#include <bits/stdc++.h>
using namespace std;

vector<int> Parent;

int Find(int x)
{
    if (Parent[x] == x) return x;
    return Parent[x] = Find(Parent[x]);
}

void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);

    if (x < y) Parent[y] = x;
    else if (x > y) Parent[x] = y;
}

int solution(int n, vector<vector<int>> computers) {
    Parent.resize(n);
    for (int i = 0; i < n; i++) {
        Parent[i] = i;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if (computers[i][j]) Union(i, j);
        }
    }

    set<int> s;
    for (int p : Parent) {
        s.insert(Find(p));
    }
    return s.size();
}