백준 4195번: 친구 네트워크 (C++)

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

4195번: 친구 네트워크

---

Solved By: Disjoint Set, Map

 

string으로 받아들인 값을 노드화 시키는 것에 대해서는 map을 사용해야겠다 생각했습니다. 하지만, 이들의 번호를 어떻게 매길지 감이 오지 않아 솔루션을 찾아보았습니다. (https://chanhuiseok.github.io/posts/baek-21/)

 

입력으로 받아들이면서 해당 string이 map내에 존재하지 않는다면 번호를 매겨서 map에 할당하는 방식으로 번호를 매겼습니다. 그리고, 증감연산자를 이용하여 등장한 순서대로 번호를 매길 수 있습니다.

if(m.count(a) == 0) m[a] = nodeNum++;

 

각 string 변수에 대해 번호를 매겼으므로 Disjoint Set을 이용할 수 있습니다. 우리가 알아야 할 건 입력으로 받아들인 두 string 변수가 친구 관계로 맺어지면서 그 친구 네트워크 안에는 몇 명이 존재하는지를 찾는 게 목적입니다.

 

A와 B가 주어지고, A의 친구 관계는 3명(A 포함), B의 친구 관계는 2명(B 포함)이라고 하겠습니다.

우선 A, B를 Union시켜야 합니다. 기존의 Union-Find 방식으로 A와 B의 Root를 찾습니다.

두 Root가 같다면 이미 기존의 친구 관계이니 Union을 할 필요가 없습니다.

 

두 A, B가 가지는 Root들의 친구 관계의 개수를 구합니다. 지금부터가 새로운 테크닉입니다. 원래 Union-Find는 두 노드의 root를 구해서 둘 중 작은 root를 큰 root의 root로 할당하도록 했지만 이 문제에서는 친구 관계의 개수를 기준으로 친구 관계 개수가 더 많은 root의 노드를 더 작은 root의 root로 할당해주었습니다. 그리고, 그 과정에서 더 작은 친구 관계의 개수를 더 큰 친구 관계의 개수를 가지는 노드의 친구 관계 개수에 더해줍니다.

-> Union 끝

->> Union을 하는 과정에서 평소의 기준(더 작은 노드 번호를 root로 두던 방식)과는 다른 기준을 가지고 서로 다른 노드의 root를 할당하는 방식이 새로운 테크닉으로 다가왔다. 그러면서 친구 관계의 개수도 구하는 게 신기했다.

void unionNodes(int a, int b){
    a = find(a);
    b = find(b);
    
    if(a != b){
        if(sizes[a] < sizes[b]) swap(a, b);
        sizes[a] += sizes[b];
        link[b] = a;
    }
}

 

그리고, 쿼리에서는 A, B 둘 중 더 많은 친구 관계를 가지는 개수를 출력하도록 코드를 짭니다.

cout << max(sizes[p1], sizes[p2]) << '\n';

 

#include <iostream>
#include <map>
#include <vector>
#include <string>
#define MAX 200001
using namespace std;

int T;
int n;

int sizes[MAX];
int link[MAX];

int find(int node){
    if(node == link[node]) return node;
    else return link[node] = find(link[node]);
}

void unionNodes(int a, int b){
    a = find(a);
    b = find(b);
    
    if(a != b){
        if(sizes[a] < sizes[b]) swap(a, b);
        sizes[a] += sizes[b];
        link[b] = a;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> T;
    for(int t = 0; t < T; t++){
        
        // init
        // 처음에는 친구 관계에 있어서 혼자 밖에 없으니
        // 1로 초기화 한다.
        for(int i = 0; i < MAX; i++){
            sizes[i] = 1;
            link[i] = i;
        }
        
        cin >> n;
        map<string, int> m;
        int nodeNum = 1;
        for(int i = 0; i < n; i++){
            string a, b;
            cin >> a >> b;
            if(m.count(a) == 0) m[a] = nodeNum++;
            if(m.count(b) == 0) m[b] = nodeNum++;
            
            unionNodes(m[a], m[b]);
            
            int p1 = find(m[a]);
            int p2 = find(m[b]);
            
            cout << max(sizes[p1], sizes[p2]) << '\n';
        }
    }
    
    return 0;
}