[백준] 4195. 친구 네트워크

 

[문제]

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

4195번: 친구 네트워크

 

[풀이]

 

Union-Find (혹은 Disjoint-Set)을 사용해서 풀었다. 

입력 값이 문자로 주어지기 때문에 map을 사용했다. 

 

parent 배열에는 해당 index의 부모 노드 index를 저장했고

number 배열에는 부모 index를 기준으로 해당 set에 속한 노드의 개수를 저장했다.

 

map의  count 함수를 사용해 이미 존재하는 친구인지 아닌지를 확인한다.

존재하지 않는다면 새로 map에 추가해주고 전체 사람의 수인 cnt 변수에 1을 추가해준다.

 

map에서의 value 값을 기준으로 ( 노드 번호라고 생각하면 이해하기 쉬울 것 같다.) 

unit 함수를 호출

 

1. 부모 노드를 찾는다.

2. 부모 노드가 다르다면

같은 집합에 속해야 되므로 parent[idx2]  = idx1을 통해

부모를 같게 해주어 같은 집합에 속하도록 한다. 

 

 

[코드]

 

시간 : 132ms

 

#include <iostream>
#include <map>

#define MAX 200000

using namespace std;

int parent[MAX] = {0,};
int number[MAX] = {0,};

int find(int idx)
{
    if(idx == parent[idx])  return idx;
    else{
        parent[idx] = find(parent[idx]);
        return parent[idx];
    }
}

int unit(int idx1, int idx2)
{
    idx1 = find(idx1);
    idx2 = find(idx2);
    
    if(idx1 != idx2 ) // 서로 부모가 다르다면
    {
        parent[idx1] = idx2;
        number[idx2] += number[idx1];
        number[idx1]=1;
        
    }
    return number[idx2];
    
}

int main(void)
{
    int T;
    scanf("%d",&T);
    
    for(int i=0;i<T;i++){
        int N;
        scanf("%d",&N);

        map <string, int> fri;
        
        for(int j=0;j<2*N;j++)
        {
            parent[j] = j;
            number[j]=1;
        }
        
        int cnt =0;
        
        for(int j=0;j<N;j++){
            
            char str1[21],str2[21];
            scanf("%s %s",str1,str2);
            //map에 str1이 존재하지 않는다면
            if(fri.count(str1)==0)  fri[str1] = cnt++;
            int idx1 = fri[str1];
            
            if(fri.count(str2)==0)  fri[str2] = cnt++;
            int idx2 = fri[str2];
            
            printf("%d\n",unit(idx1, idx2));
        }
    }
    return 0;
}