[백준/BOJ] 1717번: 집합의 표현 ( Union-Find 알고리즘 ) - C++ 문제 풀이

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/1717

 

풀이

이 문제는 원소 a, b가 같은 집합에 포함되어 있는지, 아닌지를 출력하는 문제입니다.

 

얼핏 보면 굉장히 간단한 문제 아닌가 하는 생각이 들 수 있는데,

완전히 복잡하지는 않지만, 그렇다고 직관적으로 접근하면 시간을 잡아먹을 수도 있는 문제입니다.

 

여기서는 Union-Find 알고리즘을 사용했습니다.

이 알고리즘은 여기에서 볼 수 있습니다.

[C++] 분리 집합( Disjoint Set )과 합집합 찾기( Union-Find ) 알고리즘

 

이러한 집합을 다루는 문제는 SNS 상에서 친구 관계를 맺는 기능 등을 구현할 때 적용할 수 있을 것입니다.

예를 들어, A라는 사람과 B라는 사람이 친구 관계를 맺으면, A와 친구 관계에 있는 모든 사람들과 B와 친구 관계에 있는 모든 사람들이 새롭게 친구 관계를 갖게 하는 기능이 필요합니다.

이러한 기능을 추상적 합집합 기능으로 만들고, 

주어진 두 원소가 같은 집합에 속하는 것을 알아내는 방법을 구현하도록 구성한 것이 이 문제라고 할 수 있습니다.

 

결국, 이 문제를 풀 수 있다면, 특정 SNS에 가입한 회원들이 서로 친구 관계를 맺고 있는지, 그렇지 않은지를 구현하는 기본틀을 습득할 수 있다는 얘기가 됩니다.

 

위의 Union Find 알고리즘을 적용한 함수는 다음과 같습니다.

#define SIZE 1000000

int parent[SIZE+1];

int Find_Root( int a){	// a가 속한 집합 찾기

    if ( parent[a] == a) 
        return a;

    return parent[a] = Find_Root( parent[a]);
}

void Union( int a, int b){	// a와 b가 속합 집합 결합
    int ra = Find_Root(a);
    int rb = Find_Root(b);

    if ( ra == rb)
        return;

    parent[ra] = rb;
}

 

그리고, 위의 함수들을 사용한 main 함수는 다음과 같습니다.

int main(){

    int N = readInt();	// 원소의 개수
    int M = readInt();	// 기능 호출 횟수

    for( int i = 0; i <= N; i++){	
        parent[i] = i;  // 1개 원소로 시작하는 집합의 root 표시
    }

    for( int i = 0; i < M; i++){
        int oper = readInt();	// 함수 구분
        int a = readInt();
        int b = readInt();

        if (oper == 0){
            Union(a, b);	// 합집합 구성
        }
        else{
            // 원소 a와 b가 같은 집합에 포함되어 있는지 출력
            if ( Find_Root(a) == Find_Root(b)){
                printf("YES\n");
            }   
            else{
                printf("NO\n");
            }
        }
    }

    return 0;
}

 

소스 코드

#include <iostream>
using namespace std;

// 입출력 소스 --------------------------------------------
#define WBUF_SIZE (1 << 20)

char rbuf[WBUF_SIZE];
int ridx, nidx;

inline char read() {
	if (ridx == nidx) {
		nidx = fread(rbuf, 1, 1 << 20, stdin);
		if (!nidx) return 0;
		ridx = 0;
	}
	return rbuf[ridx++];
}
inline int readInt() {
	int sum = 0;
	char now = read();
	bool flg = false;

	while (now <= 32) now = read();
	if (now == '-') flg = true, now = read();
	while (now >= 48) sum = sum * 10 + now - '0', now = read();

	return flg ? -sum : sum;
}
//----------------------------------------------------------

#define SIZE 1000000

int parent[SIZE+1];

int Find_Root( int a){

    if ( parent[a] == a) 
        return a;

    return parent[a] = Find_Root( parent[a]);
}

void Union( int a, int b){
    int ra = Find_Root(a);
    int rb = Find_Root(b);

    if ( ra == rb)
        return;

    parent[ra] = rb;
}

int main(){

    int N = readInt();
    int M = readInt();

    for( int i = 0; i <= N; i++){
        parent[i] = i;  // root 
    }

    for( int i = 0; i < M; i++){
        int oper = readInt();
        int a = readInt();
        int b = readInt();

        if (oper == 0){
            Union(a, b);
        }
        else{
            if ( Find_Root(a) == Find_Root(b)){
                printf("YES\n");
            }   
            else{
                printf("NO\n");
            }
        }
    }

    return 0;
}