4195 친구 네트워크

4195 친구 네트워크 (c++)

문제

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

접근 방식

Union Find

1. 테스트 케이스 T번 반복
2. 친구의 관계가 F번 입력됨
3. 해당 둘의 관계 네트워크 안에 몇명의 사람이 있는지를 출력 -> Union 하면서 총 node의 갯수를 확인

문제 풀이

#include <iostream>
#include <string>
#include <map>
#define endl '\n'
using namespace std;
int order;
map<string, int> m;
int nodeCount[200'000];
int p[200'000];
int Find(int x)
{
    if (p[x] == x) return x;

    return p[x] = Find(p[x]);
}
int Union(int a, int b)
{
    a = Find(a);
    b = Find(b);
    if (a == b) return nodeCount[a];
    else if (nodeCount[a] < nodeCount[b])
    {
        nodeCount[b] += nodeCount[a];
        nodeCount[a] = 1;
        p[a] = b;

        return nodeCount[b];
    }
    else
    {
        nodeCount[a] += nodeCount[b];
        nodeCount[b] = 1;
        p[b] = a;

        return nodeCount[a];
    }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T, F; cin >> T;
    string a, b;
    while (T-- > 0)
    {
        cin >> F;
        m.clear();
        order = 0;
        while (F-- > 0)
        {
            cin >> a >> b;
            int A, B;
            if (m.find(a) == m.end())
            {
                m[a] = order;
                p[order] = order;
                nodeCount[order++] = 1;
            }
            if (m.find(b) == m.end())
            {
                m[b] = order;
                p[order] = order;
                nodeCount[order++] = 1;
            }
            A = m[a]; B = m[b];
            cout << Union(A, B) << endl;
        }
    }

    return 0;
}

다시 생각해볼 점

1. 이번건 Union Find의 Advance 단계인 ‘총 노드 수 세기’ 알고리즘이었다.
2. Union Find는 Disjoint Set(서로소 집합)의 연산 알고리즘이기 때문에
   1. 만약 두 노드의 루트가 같다면 이미 포함관계이므로 루트의 노드를 반환
   2. 만약 두 노드의 루트가 같지 않다면 서로소 관계이므로 머지해주면서 두 노드의 노드 수의 합을 저장 후 반환 (겹치는게 없으므로 그냥 더해주기만 해도 됨)
3. 이 때 발생하는 문제는 입력이 string이기때문에 int p[N]으로 접근할 수 없다는 것이었다.
   1. 그래서 Map<string, int> 를 하나 생성하여 이미 값이 존재한다면 반환해주고 없다면 m[str] = order++ 해서 반환해줬다.
   2. 하지만 중간에 string -> int? 이거 해쉬해주면 좋을텐데라는 생각이 들었고
   3. 찾아보니 상위권 코드들은 해쉬테이블을 이용한 구조가 많았다.
4. 다음엔 Hash Table 관련 알고리즘도 더 공부해봐야겠다.