[백준/BOJ] 4195번: 친구 네트워크 ( Union-Find 알고리즘 ) - C++ 문제 풀이

문제 설명

 

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

 

풀이

이 문제는 주어진 두 사람이 친구 관계를 맺었을 때, 이 두 명이 속한 친구 집합의 인원수를 출력하는 문제입니다.

 

여기서는 Union-Find 알고리즘을 사용해서 문제를 풀었습니다.

Union-Find은 분리 집합들을 결합하고, 주어진 원소가 속한 집합을 찾아내는 방법에 관한 알고리즘입니다.

 

Union-Find 알고리즘은 여기에 정리하였습니다.

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

 

먼저, 읽어보면 나머지를 쉽게 이해할 수 있습니다.

 

이 문제에서는, SNS에 가입한 사람 이름을 입력받아, 친구 집합을 구성해야 합니다.

그런데, 이름 문자열을 그대로 사용하면, 불필요한 자원을 사용해야 하므로, 이름을 id 번호로 바꿀 수 있도록 맵을 사용 했습니다.

이 과정을 코드로 작성하면 다음과 같습니다.

#define SIZE 2000000

int parent[SIZE];   // 각 원소의 부모 원소 기록
int members[SIZE];  // 원소가 속한 집합의 총 원소 개수
int cnt = 0;    // 현재까지 맵에 추가한 원소의 개수

// 사용자를 id로 변환
typedef unordered_map<string, int> MYMAP;

int Find_Group( MYMAP& um, const string& p){

    MYMAP::iterator iter = um.find(p);
    
    int id;
    if ( iter == um.end()){ // 사용자가 등록되지 않았으면 id등록
        id = cnt++;
        um.emplace( p, id );

        parent[id] = id;    // 등록된 id로 집합 생성
        members[id] = 1;    // 생성된 집합의 원소 개수 초기화
    }
    else{
        id = iter->second;  // 이전에 등록된 사용자이면, 등록된 id 반환
    }

    return id;
}

이 함수는 이름을 입력받아, 등록된 id로 변환하는 함수입니다.

만약, 등록된 id가 없으면, 새로이 id를 등록하고, 이 id를 원소로 가지는 집합을 생성합니다.

 

맵에 원소를 생성하기 위해, insert대신 emplace 함수를 사용했습니다.

emplace함수는 주어진 데이터를 가지고 내부 삽입을 수행하기 때문에, pair <사용자, id> 객체를 구성할 필요가 없습니다.

이 함수에 대한 내용은 여기에 정리하였습니다.

[C++] STL emplace 함수 설명 및 사용법

 

위에 링크한 Union-Find 알고리즘을 구현한 코드입니다.

이 문제는 집합이 가진 원소의 개수를 알아내는 것이므로,

두 집합을 합치는 Union 함수에서 두 집합을 연결하는 것 외에,

두 집합이 가진 원소들의 개수를 합쳐서 기록하고, 이 개수를 반환하도록 변경했습니다.

int Find_Root( int a){

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

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

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

    if ( ra != rb){
        
        parent[ra] = rb;
        members[rb] += members[ra];	// a와 b 집합의 원소 개수 합침
    }

    return members[rb];	// b가 속한 집합의 원소 개수
}

 

마지막으로, 이 함수를 사용해서, 사용자가 입력될 때마다 친구 관계를 맺고, 이 두 친구가 속한 집합의 원소 개수를 반환하는 코드입니다.

int main(){
   
    MYMAP um;	// 사용자를 id로 변환하기 위한 map
    
    int nShowCase;
    int F;

    cin >> nShowCase;
    string p1, p2;

    for(int i = 0; i < nShowCase; i++){

        cin >> F;	// 친구 맺기 횟수

        for( int j = 0; j < F; j++){
            
            cin >> p1 >> p2;	// 두 친구 입력
            
            int g1 = Find_Group(um, p1);
            int g2 = Find_Group(um, p2);

            int members = Union(g1, g2);	// 친구 관계 맺기

            cout << members << endl;	// 두 친구가 속한 집합의 원소 개수
        }

        // clear previous data
        um.clear();
        memset( parent, 0, sizeof(int)*SIZE);
        memset( members, 0, sizeof(int)*SIZE);
        cnt = 0;
    }

    return 0;
}

 

소스 코드

#include <iostream>
#include <unordered_map>
#include <string.h>
using namespace std;

#define SIZE 2000000

int parent[SIZE];
int members[SIZE];
int cnt = 0;

typedef unordered_map<string, int> MYMAP;

int Find_Group( MYMAP& um, const string& p){

    MYMAP::iterator iter = um.find(p);
    
    int id;
    if ( iter == um.end()){
        id = cnt++;
        um.emplace( p, id );

        parent[id] = id;
        members[id] = 1;
    }
    else{
        id = iter->second;
    }

    return id;
}

int Find_Root( int a){

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

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

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

    if ( ra != rb){
        
        parent[ra] = rb;
        members[rb] += members[ra];
    }

    return members[rb];
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    MYMAP um;
    
    int nShowCase;
    int F;

    cin >> nShowCase;
    string p1, p2;

    for(int i = 0; i < nShowCase; i++){

        cin >> F;

        for( int j = 0; j < F; j++){
            
            cin >> p1 >> p2;
            
            int g1 = Find_Group(um, p1);
            int g2 = Find_Group(um, p2);

            int members = Union(g1, g2);

            cout << members << endl;
        }

        // clear previous data
        um.clear();
        memset( parent, 0, sizeof(int)*SIZE);
        memset( members, 0, sizeof(int)*SIZE);
        cnt = 0;
    }

    return 0;
}