[BOJ] 4195번 : 친구 네트워크

김영한·2021년 2월 26일
0

알고리즘

목록 보기
6/74

문제 링크 : 백준 4195번

[문제 접근]

Union-Find를 통해 풀 수 있는 문제였는데 인덱스 대신에 사람 이름으로 주어져서 map을 이용해서 임의로 인덱스를 추가해주었다.

  1. 처음 등장한 사람에게는 새로운 인덱스를 할당한다.
  2. 한 번 등장했던 사람은 map에서 인덱스를 찾는다.
  3. 같은 네트워크에 있다면 해당 네트워크 크기를 출력해준다.
  4. 다른 네트워크에 있다면 네트워크를 합친 후 크기를 출력해준다.

[소스 코드]

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;
int t;
int parent[200001];
int netSize[200001];

int Find(int node) {
    if(node == parent[node]) return node;

    return parent[node] = Find(parent[node]);
}

void Union(int node1, int node2) {
    node1 = Find(node1);
    node2 = Find(node2);

    if(node1 != node2) {
        if(netSize[node1]<netSize[node2]) swap(node1, node2);

        parent[node2] = node1;
        netSize[node1] += netSize[node2];
        netSize[node2] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        map<string, int> m;
        int index=0;
        for(int i=0 ; i<200001 ; i++) {
            parent[i] = i;
            netSize[i] = 1;
        }

        for(int i=0 ; i<n ; i++) {
            string s1, s2;
            cin >> s1 >> s2;
            if(m.find(s1) == m.end()) m[s1] = index++;
            if(m.find(s2) == m.end()) m[s2] = index++;

            int test1 = Find(m[s1]);
            int test2 = Find(m[s2]);

            if(test1 == test2) { // 같은 네트워크
                cout << max(netSize[test1], netSize[test2]) << "\n";
            }
            else { // 다른 네트워크
                Union(test1, test2); // 합치고
                cout << max(netSize[test1], netSize[test2]) << "\n";
            }
        }
    }
    
    return 0;
}

0개의 댓글