https://www.acmicpc.net/problem/1717

문제

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

예제 입출력

• 예제 입력

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

• 예제 출력

NO
NO
YES

Solution

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 1000001
using namespace std;

int N, M;
int Parent[MAX];

int getParent(int num){
    if(num == Parent[num]) return num;
    return Parent[num] = getParent(Parent[num]);
}

void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a != b) Parent[a] = b;
}

bool findParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a == b) return true;
    else return false;
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> M;
    for(int i = 1; i <= N; i++) Parent[i] = i;
    for(int i = 0; i < M; i++){
        int num, a, b;
        cin >> num >> a >> b;
        if(num == 0) unionParent(a, b);
        else if(num == 1){
            if(findParent(a, b)) cout << "YES\n";
            else cout << "NO\n";
        }
    }
    return 0;
}

Union Find 알고리즘을 활용한 문제. Tree를 활용해야 하는 문제다.

다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

이 문단에 주목. 입력 예시를 자세히 살펴보자.

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

총 1부터 7까지의 숫자들이 주어진다. 그리고 총 8 번의 입력에서 0 a b 형태로 값이 주어지면 a가 포함된 집합과 b가 포함된 집합을 합친다는 의미다. 어렵게 생각할 것 없이 Tree 구조를 만들어 준다고 생각하면 편하다. 똑같은 Parent 산하로 둔다는 의미로 받아들이면 된다.
1 a b 연산이 실행된다면 a와 b가 같은 집합에 있는가를 확인한다. 같은 parent를 가지고 있는가? 를 확인한 후 맞다면 true, 아니라면 false 를 리턴한다.
아무것도 명령이 입력되지 않은 상황에선 그냥 숫자들이 자유롭게 자리잡고 있을 것이다. 0 명령이 하나라도 들어간다면 그 이후부터 집합이 생기기 시작한다.

void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a != b) Parent[a] = b;
}

0 명령이 실행된다면 처음에는 각 인덱스마다 Parent가 없어서 각자 본인의 인덱스 값이 Parent배열에 저장되어 있다. 만약 두 노드의 Parent값이 다르다면 a노드에 b의 Parent값을 대입해버린다.

int getParent(int num){
    if(num == Parent[num]) return num;
    return Parent[num] = getParent(Parent[num]);
}

위의 함수는 해당 노드의 Parent 값을 리턴하는 함수. 만약 패러미터와 패러미터에 위치한 노드의 Parent값이 같다면 그냥 그 값을 리턴, 아니라면 해당 위치에 실제로 어떤 값이 있는 지 찾아본 후 다시 리턴한다.

bool findParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a == b) return true;
    else return false;
}

1 명령이 실행되면 위의 함수가 실행된다. 간단하다. 두 노드의 Parent가 다르다면 false를 리턴한다.

Union Find 알고리즘을 연습해볼 수 있는 문제다. 조금 고급진 알고리즘을 활용했기에 골드 난이도로 책정된 듯 하다.