4195번

4195번 - 친구 네트워크

이 문제는 union-find 를 이용해서 문제를 풀었다. 추가적으로 STL 의 map 을 이용했다.

다른 분들 코드를 보니 각 노드에 번호를 다시 매겨서 그 번호를 이용해서 문제를 푸신다.

나는 map 에서 string 을 배열의 인덱스로 사용할 수 있으니 , 그냥 string 을 사용해서 문제를 풀었다.

(그런데 이게 다른 문제에서는 메모리 오류나, 시간 오류가 발생하는 지는 모르겠다 <-- 확인해볼 사항)

그리고 사이즈를 구하는 배열을 따로 추가해서, 각 트리의 사이즈를 알 수 있게 만들어서, 그걸 출력했다.

그런데 여러가지 궁금증 발생 => 아래 질문들

갓들은 대단하다 정말.....

<내가 올린 질문>

<답변>

<정답 코드 - 질문 후>

#include<iostream>
#include<vector>
#include<map>
#include<string>
using namespace std;
 
map<string,string> prt;
map<string,int> s;
map<string,int> r;
 
 
string find(string x)
{
    if (x == prt[x])
    {
        return x;
    }
 
    return prt[x] = find(prt[x]);
}
void merge(string x, string y)
{
    x = find(x);
    y = find(y);
    if (x == y)
    {
        return;
    }
 
    if (r[x] > r[y]) { swap(x, y); }
 
    prt[x] = y;
 
    if (r[x] == r[y]) { r[y]++; }
 
    s[y] += s[x];
 
    return;
}
int main()
{
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; t++)
    {
        int N;
        prt.clear();
        s.clear();
        r.clear();
        cin >> N;
        
        for (int i = 0; i < N; i++)
        {
            char a[30];
            char b[30];
            scanf("%s",a);
            scanf("%s",b);
            
            if (prt.count(a) == 0)
            {
                prt[a] = a;
                s[a] = 1;
                r[a] = 1;
            }
            if(prt.count(b)==0)
            {
                prt[b] = b;
                s[b] = 1;
                r[b] = 1;
            }
 
            merge(a, b);
 
            printf("%d\n", s[find(a)]);
        }
 
    }
    
    return 0;
}

<정답 코드 - 질문 이전>

#include<iostream>
#include<vector>
#include<map>
#include<string>
using namespace std;
 
map<string, string> prt;
map<string,int> s;
 
string find(string x)
{
    if (x == prt[x])
    {
        return x;
    }
 
    return prt[x] = find(prt[x]);
}
void merge(string x, string y)
{
    x = find(x);
    y = find(y);
    if (x == y)
    {
        return;
    }
 
    prt[x] = y;
    s[y] += s[x];
    
 
    return;
}
int main()
{
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; t++)
    {
        int N;
        s.clear();
        prt.clear();
        cin >> N;
        
        for (int i = 0; i < N; i++)
        {
            char a[30];
            char b[30];
            scanf("%s",a);
            scanf("%s",b);
            
            if (prt.count(a) == 0)
            {
                prt[a] = a;
                s[a] = 1;
            }
            if(prt.count(b)==0)
            {
                prt[b] = b;
                s[b] = 1;
            }
 
            merge(a, b);
 
            printf("%d\n", s[prt[b]]);
        }
 
    }
    
    return 0;
}