백준 4195 친구 네트워크

문제 링크

이 문제는 union-find를 사용하는 문제이다.

다만 2가지를 고려해야한다.

• 숫자가 아닌 이름이 입력으로 줌 -> 이를 숫자로 바꿀 수 있는 로직이 필요
• 해당 root에 몇 명이 포함되어 있는지 저장해야함

1. 이름을 string으로 바꾸기 위해 map을 사용했고, 이 로직이 O(1)이도록 하기 위해 unordered_map 자료구조 (hashmap)을 사용했다.

2. 특정 root에 몇명이 있는지 알기 위해 vector를 사용했다.

이 문제는 F가 최대 100000가 주어진다

고로 worst case에는 모두 다른 사람이 들어올 수 있으므로 map과 vector의 크기를 200000으로 초기화 해야한다.

#define FASTIO ios::sync_with_stdio(false); cout.tie(0); cin.tie(0);

#include<iostream>
#include<vector>
#include<unordered_map>
#include<stdlib.h>

using namespace std;

/**
 * union-find 문제
 * 이름 : id를 저장하는 hash-map -> nameToId (name -> id)
 * root에 해당 집합에 몇 명이 있는지 저장 -> numberOfGroup 배열 (루트 id ->사람 수)
 */

int id;
int F;

vector<int> parent(200'001);
vector<int> numberOfGroup(200'001);
unordered_map<string, int> nameToId;

int findParent(int a){
    if(a == parent[a]) return a;
    return parent[a] = findParent(parent[a]);
}

int unionGroup(int a, int b){ // 병합 + 그룹 내의 사람 수 리턴
    a = findParent(a);
    b = findParent(b);

    if(a==b) return numberOfGroup[a];

    parent[a] = b;
    return numberOfGroup[b] = numberOfGroup[b] + numberOfGroup[a];
}

int makeOrGetIdx(string name){
    if(nameToId.find(name) == nameToId.end()){ // 처음인 경우
        nameToId.insert(make_pair(name, id)); // insert는 pair로 전달해야 한다. 아니면 []도 가능
        return id++;
    }
    return nameToId[name];
}

void init(){
    id = 0;
    nameToId.clear();
    fill_n(numberOfGroup.begin(), 200'001, 1);
    for(int i = 0; i <= 200'001; i++){
        parent[i] = i;
    }
}

int main(){
    FASTIO

    int T;
    cin >> T;
    for(int test_case = 1; test_case <= T;test_case++){ 
        cin >> F;
        init(); //test_case 마다 초기화 해야 함
        for(int i = 0; i < F;i++){
            string name1, name2;
            cin >> name1 >> name2;
            int idx1 = makeOrGetIdx(name1);
            int idx2 = makeOrGetIdx(name2);
            cout << unionGroup(idx1, idx2) << endl;
        }
    }
    return 0;
}

unordered map에 삽입을 위해 insert를 사용하면 pair를 통해서 전달해야 한다.

이미 key가 있는 경우에는 insert가 무시되기 때문에 정보를 수정하려면 오버로딩 되어있는[]연산자를 사용해야 한다.