[백준] 1717번 : 집합의 표현

문제

 

---

풀이

 

유니온 파인드로 푸는 문제다.

약...2년전 자료구조 시간에 배웠는데

그때 당시에는 아는 것도 없고 + 영어 강의고 + 기타 등등의 이유로 개념만 정말 간신히 익힌 것 같다.

 

지금 내가 설명하기엔

ssungkang.tistory.com/entry/Algorithm-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9CUnion-Find

[Algorithm] 유니온 파인드(Union - Find)

이 분이 정말 완벽하게 설명하셨다.

자료구조를 배울 때 이걸 봤으면 내가 유니온 파인드와 좀 더 금방 친해졌을텐데...

---

소스코드

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> parent;

int findParent(int x) { //parent[x]가 음수가 될 때까지(root에 다다를 때까지) 재귀 함수 호출
    if (parent[x] < 0)
        return x;
    return parent[x] = findParent(parent[x]);
}

void unionInput(int x, int y) {
    int x_p = findParent(x); //x의 부모
    int y_p = findParent(y); //y의 부모

    if (x_p == y_p) //이미 같은 집합
        return;
    if (parent[x_p] < parent[y_p]) { //x_p를 root로 하는 노드가 더 많으면 x_p -> y_p
        parent[x_p] += parent[y_p];
        parent[y_p] = x_p;
    } else { //y_p를 root로 하는 노드가 더 많으면 y_p -> x_p
        parent[y_p] += parent[x_p];
        parent[x_p] = y_p;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, cmd, a, b;

    cin >> n >> m;
    parent.assign(n + 1, -1);
    for (int i = 0; i < m; i++) {
        cin >> cmd >> a >> b;
        if (cmd == 0)
            unionInput(a, b);
        else {
            if (findParent(a) == findParent(b))
                cout << "YES\n";
            else
                cout << "NO\n";
        }
    }
}

 

유니온 파인드 알고리즘은 노드 2개를 합치는 유니온 함수와 그 노드들의 부모를 찾는 파인드 함수로 이루어진다.

 

    parent.assign(n + 1, -1);

메인에서 먼저 parent 벡터를 전부 -1로 초기화 한다.

모든 노드의 초기상태는 자기 스스로를 root로 하고, 그 집합의 크기가 1인 상태라는 뜻이다.

 

    for (int i = 0; i < m; i++) {
        cin >> cmd >> a >> b;
        if (cmd == 0)
            unionInput(a, b);
        else {
            if (findParent(a) == findParent(b))
                cout << "YES\n";
            else
                cout << "NO\n";
        }
    }

명령어가 0이냐 1이냐에 따라서 유니온을 하거나 파인드를 한다.

먼저 파인드 함수를 보자

 

int findParent(int x) { //parent[x]가 음수가 될 때까지(root에 다다를 때까지) 재귀 함수 호출
    if (parent[x] < 0)
        return x;
    return parent[x] = findParent(parent[x]);
}

그냥 간단한 재귀함수로 구현했다.

parent[x]가 음수면 root라는 뜻이니 x를 반환하고, 그렇지 않을 경우 parent[x]를 갱신하며 root를 찾는다.

 

갱신을 한다는 것이 굉장히 중요한데...

이걸 이렇게 바꿔주는 것이다.

이 과정을 거치지 않으면 지금이야 3->1로 갈 수 있는 걸 3->2->1로 가는 것에 그치지만

노드가 많아지면 부모를 찾는 과정이 길어질 것이고 곧 시간초과로 이어질 것이다.

 

void unionInput(int x, int y) {
    int x_p = findParent(x); //x의 부모
    int y_p = findParent(y); //y의 부모

    if (x_p == y_p) //이미 같은 집합
        return;
    if (parent[x_p] < parent[y_p]) { //x_p를 root로 하는 노드가 더 많으면 x_p -> y_p
        parent[x_p] += parent[y_p];
        parent[y_p] = x_p;
    } else { //y_p를 root로 하는 노드가 더 많으면 y_p -> x_p
        parent[y_p] += parent[x_p];
        parent[x_p] = y_p;
    }
}

유니온 함수에선 일단 각 노드 x, y의 부모를 찾아준다.

부모가 같다면 이 노드들은 이미 같은 집합에 있는 것이니 유니온 할 필요가 없다.

 

x_p, y_p는 root기 때문에 parent의 값이 음수일 것이다.

그리고 그 값의 절댓값이 x_p, y_p를 root로 한 집합의 크기다.

 

parent[x_p]<parent[y_p] 라면, 예를 들어 parent[x_p]=-4이며 parent[y_p]=-2라면 x_p를 root로 한 집합이 더 큰 것이다.

그럼 x_p를 새로운 root로 만들고 y_p를 그 자식으로 넣어준다.

 

parent[x_p]>parent[y_p] 라면, 반대로 하면 되겠다.