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

문제 및 풀이

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

Union-Find 알고리즘을 응용한 문제 !

1. 이 문제는 string 형태로 node가 주어진다. 따라서 이를 숫자 index로 치환해서 연산해야 한다. string 마다 고유한 int value값을 가지는 형태이므로 map을 사용해서 코드를 작성했다.

2. 문제에서 정의한 친구 네트워크가 뭔지 이해가 안가서...🤷‍♀️ TC보고 일반화해서 풀었다

   • 두 친구가 이미 간선으로 연결된 경우 : 간선에 연결된 모든 노드들이 답
   • 두 친구가 연결되지 않은 경우 : (a와 연결된 노드의 수) + (b와 연결된 노드의 수)

   다만 일반적인 Union-Find와 다르게 이 문제는 연결된 노드들의 갯수를 찾기 위해 배열을 하나 더 정의해서 사용해야 했다. (매번 연결된 노드를 계산하면 시간초과 났다;;;)
   현재 노드와 연결된 노드의 갯수(자기 자신 포함해서 초기값 1)로 정의되는 배열 cnt를 정의했고 두 노드가 merge될 때 마다 부모 index가 작은쪽으로 수를 몰아주도록 작성했다.

    if(a<b) {
        parents[b]=a;
        cnt[a]+=cnt[b];
    }

코드

#include <iostream>
#include <map>
using namespace std;

const int MAX = 200001;

int T,n;
string str1, str2;
int parents[MAX];
int cnt[MAX];


int getParent(int x){
    if(parents[x]==x) return x;
    else return parents[x] = getParent(parents[x]);
}


void merge(int a, int b){
    a = getParent(a);
    b = getParent(b);

    if(a==b) return ;

    if(a<b) {
        parents[b]=a;
        cnt[a]+=cnt[b];
    }
    else {
        parents[a]=b;
        cnt[b]+=cnt[a];
    }

}


bool isSame(int a, int b){
    return getParent(a) == getParent(b);
}



int main(){

    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin>>T;

    while(T--){
        cin>>n;
        int index=1;
        map<string, int> m;
        fill(cnt, cnt+MAX, 0);

        for(int i=0; i<n; i++){
            cin>>str1>>str2;

            if(m.count(str1)==0) {
                m[str1]=index;
                parents[index]=index;
                cnt[index]=1;
                index++;
            }
            if(m.count(str2)==0) {
                m[str2]=index;
                parents[index]=index;
                cnt[index]=1;
                index++;
            }

            int a = m[str1];
            int b = m[str2];

            if(isSame(a,b)){
                cout<<cnt[getParent(a)]<<'\n';
            }
            else {
                cout<<cnt[getParent(a)]+cnt[getParent(b)]<<'\n';
                merge(a,b);
            }


        }
    }


}