[백준/C++] 친구 네트워크 (No. 4195)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 친구 관계가 생길 때 마다 두 사람의 친구 네트워크의 합을 출력하는 문제다.

 

즉, 두 집합의 합집합의 결과를 출력하는 문제와 같다.

 

문제에서는 친구 관계가 연결되면, string으로 친구 관계가 주어진다.

그러므로 좀 더 편하게 문제를 풀기 위해 unordered_map을 이용해 string을 int로 변환하고 이 int를 index로 사용했다.

 

index로 변환하는 방법은 처음 나타난 친구라면 map에 저장된 int가 0이다.

그러므로 map[string]==0일 경우에는 index를 저장해주고 아니라면, 그대로 진행했다.

 

index를 할당한 다음에는 두 집합을 합쳐야한다.

 

두 집합을 합치는 방법은 union-find 알고리즘을 이용했다.

 

 

이때, 두 사람이 원래 친구로 연결되어 있다면, 두 집합의 대표 원소는 같다.

반면, 두 사람이 원래 친구로 연결되어 있지 않다면, 두 집합의 대표 원소가 다르다.

 

이렇게 두 집합이 합쳐지는 경우에는 가장 작은 index를 그 집합의 대표원소로 정하고, 두 집합의 인원을 합치도록 코드를 구현했다.

 

이 과정을 친구 관계가 생길 때 마다 반복하면 쉽게 풀 수 있는 문제다.

 

 

​

[아이디어 정리]

1. 처음 등장한 친구인지 판단하고, 만약 처음 등장한 친구라면 map을 이용해 index를 부여한다.
2. 두 친구가 원래 연결된 상태라면 집합의 대표원소가 같으므로, 그 집합의 인원을 출력한다.
3. 두 친구가 원래 연결되지 않았다면, 집합의 대표원소가 다르므로, 더 작은 원소를 집합의 대표원소로 하고 두 집합의 인원을 합친다.
4. 위 과정에서 대표원소를 찾는 방법은 union-find 알고리즘으로 구한다.

 

 

 

Code

 

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
#include <unordered_map>
using namespace std;

int FindPar(int n,vector<pair<int,int>> &par) {
    if (n == par[n].first) {
        return n;
    }
    return par[n].first=FindPar(par[n].first, par);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    for (int t = 0; t < tc; t++) {
        int n;
        cin >> n;
        string f1, f2;
        unordered_map<string, int> fIdx;
        int nowMapNum = 1;
        vector<pair<int,int>> par(200001);
        for (int i = 0; i < n; i++) {
            cin >> f1 >> f2;
            if (fIdx[f1] == 0) {
                par[nowMapNum].first=nowMapNum,par[nowMapNum].second=1;
                fIdx[f1] = nowMapNum++;
            }
            if (fIdx[f2] == 0) {
                par[nowMapNum].first = nowMapNum, par[nowMapNum].second = 1;
                fIdx[f2] = nowMapNum++;
            }
            int pf1 = FindPar(fIdx[f1], par), pf2 = FindPar(fIdx[f2], par);
           if (pf1<pf2)
           {
               par[pf1].second += par[pf2].second;
               par[pf2].first = pf1;
               cout << par[pf1].second<<"\n";
           }
            else if (pf1>pf2)
            {
                par[pf2].second += par[pf1].second;
                par[pf1].first = pf2;
                cout << par[pf2].second << "\n";
            }
            else
            {
                cout << par[pf1].second << "\n";
            }
        }
    }
   
    return 0;
}

 

---

map 과 union-find알고리즘을 적절히 사용하면 쉽게 풀 수 있는 문제였다.