[백준/C++] #4195 친구 네트워크 (Union Find)

문제

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

힣 이제 플레다!!

 

구상

친구 관계가 주어지고, 친구 네트워크에 몇 명이 있는지 구해내는 문제였다. 그래서 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하는 Disjoint Set 자료구조를 사용해야겠다 싶었고, Disjoint Set를 표현하기 위해서 Union Find 알고리즘을 사용해야했다. Union Find에서 집합(네트워크)을 구현할 때 벡터, 배열, 맵 등의 자료구조를 이용할 수 있는데, 나는 unordered map을 선택했다. 처음에 벡터를 이용하는 방식으로 구현했었는데, 불필요하게 벡터의 크기가 커졌다. 그래서 네트워크를 표현하는 딱 필요한 연결리스트만 표현하기 위해서는 map을 사용하면 좋겠다는 생각이 들었고, 데이터들의 순서는 상관이 없었기에 unordered map을 이용하여 구현했다.

 

그리고, 네트워크 크기를 출력해야해서 네트워크 그룹 크기를 저장해야했다. 이 또한 메모리와 탐색 시간을 줄이기 위해 unordered map을 사용하여, 루트 노드에 해당 루트 노드가 포함된 네트워크 크기를 매핑하여 저장하도록 했다. 

*unordered map에서 데이터에 접근하거나 삽입하거나 삭제할 때는 O(1)의 시간복잡도가 소요된다. 

 

Union Find의 개념에 대해서는 아래 블로그를 참고했다. 

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

[알고리즘] Union-Find 알고리즘 - Heee's Development Blog

 

풀이 + 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<unordered_map>
#define INF 100001
#define endl "\n"
using namespace std;
/*
4195 친구 네트워크
친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램
*/

int T;
unordered_map<string, string> root; // 연결 리스트
unordered_map<string, int> groupSize; // 그룹의 크기

string find(string x) {
    // 루트 노드는 부모 노드 번호로 자기 자신을 가짐
    if (root[x] == x) {
        return x;
    }
    else {
        // 각 노드의 부모 노드를 찾아 올라감
        return root[x] = find(root[x]); // 경로 압축 최적화    
    }
}

void uni(string x, string y) {
    x = find(x); // 초기화
    y = find(y);
    
    if (x == y) return;

    root[y] = x;
    groupSize[x] += groupSize[y]; // 그룹의 크기를 합침
}

void solution() {
    while (T--) {
        root.clear(); 
        groupSize.clear();

        int num;
        cin >> num;
        for (int i = 0; i < num; i++) {
            string a, b;
            cin >> a >> b;
            if (root.count(a) == 0) { // 새로운 친구
                root.insert({ a, a });
                groupSize[a] = 1;
            }
            if (root.count(b) == 0) { // 새로운 친구
                root.insert({ b, b });
                groupSize[b] = 1;
            }

            uni(a, b); // 친구로 엮기

            // a와 b가 속한 union에 노드 개수 출력
            cout << groupSize[find(a)] << endl;
        }
        
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> T;

    // 로직
    solution();

    return 0;

}