[해시/union-find 알고리즘] BAEKJOON ' 4195'번 '친구 네트워크 '문제 (C++/python)

문제 : www.acmicpc.net/problem/4195

4195번: 친구 네트워크

 

 

 

• 문제 해결 아이디어

    1.  union-find 알고리즘을 사용하여 문제를 해결한다.

   

    2.  자신의 상위 노드를 저장하는 배열 하나와, 자신의 현재 네트워크를 저장하는 배열을 선언한다.

   

    3.  2명의 이름을 입력받고, 새로 들어온 사람이라면 상위노드를 자기자신, 네트워크 수를 1로 초기화한다.

 

    4.  find함수를 이용하여 해당 이름의 최상위 노드값을 찾아내고, 두 최상위 노드를 비교하여 다르다면 (다른 집합이라면)
         두 그룹을 합쳐준다. (최상위 노드가 각각 a,b라면 b의 최상위 노드를 a로 지정하는 식으로 합칠 수 있다.)

 

    5.  입력받은 이름들이 속해있는 그룹의 최상위 노드의 네트워크 수를 출력해준다.

 

    6. union-find 알고리즘에 대한 자세한 설명은 gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html에서 확인할 수 있다.

 

 

 

• python

def find(person):
    if person == root[person]:
        return person
    else:
        p = find(root[person])
        root[person] = p
        return root[person]

def union(person1, person2):
    person1_root = find(person1)
    person2_root = find(person2)

    if person1_root != person2_root:
        root[person2_root] = person1_root
        net_number[person1_root] += net_number[person2_root]





test_case = int(input())

for _ in range(test_case):
    root = dict()
    net_number = dict()

    F = int(input())

    for _ in range(F):
        person1,person2 = input().split(' ')

        if person1 not in root:
            root[person1] = person1
            net_number[person1] = 1

        if person2 not in root:
            root[person2] = person2
            net_number[person2] = 1

        union(person1, person2)
        print(net_number[find(person1)])

 

※ dictionary 자료형

 

    key값과 value값으로 이루어져있다. (key값은 변할 수 없고, value값은 변경 가능하다.)

    set, dict, list같은 값들은 key로 사용할 수 없다.

>>> root = dict()
>>> root['Fred'] = 'Fred'
>>> root['Barney'] = 'Fred'
>>> root[1] = 'Barney'
>>> root
{'Fred': 'Fred', 'Barney': 'Fred', 1: 'Fred'}

순서는 따로 없기때문에 index로 접근은 불가능하다. (key값으로 접근해야된다.)

 

 

if 'Fred' not in root:

위와 같은 방법으로 root에 해당 key값이 있는지 확인할 수 있다.

 

value를 확인하고싶다면 다음과 같이 확인할 수 있다.

if 'Fred' not in root.values():

 

 

for문에서 사용

 

key접근

>>> root = {'Fred':'Fred', 'Fred':'Tomas'}
>>> for key in root:
...     print(key)
Fred
Fred

 

value접근

>>> root = {'Fred':'Fred', 'Fred':'Tomas'}
>>> for value in root.values:
...     print(value)
Fred
Tomas

 

추가적인 사용법은 wikidocs.net/16043 에서 더 확인할 수 있다.

 

 

 

 

 

• c++

    c++에선 python의 dictionary와 같은 방법으로 map을 사용한다.

    초기에 구조체와 포인터를 이용하여 tree를 구현하는 식으로 진행하다 더 간단한 배열을 이용하기로 하였다.

    배열을 사용하기 위해 map을 string과 int로 구성하였고 int부분을 index로 활용하였다.

 

#include "iostream"
#include "map"

using namespace std;

#define maximum 200001

int networks[maximum];
int root[maximum];
int idx=0;


// 입력받은 index의 최상위 노드의 index가 무엇인지 찾아내고 그를 반환한다.
// else부분에서, 최대한 재귀함수가 적게돌도록 하기 위해서, root값을 재지정해준다.
int find_root(int x){
    if(x == root[x])
        return x;
    
    else{
        int new_root = find_root(root[x]);
        root[x] = new_root;
        return root[x];
    }
}

// find_root를 통해 반환받은 값을 이용하여 같은 그룹인지 확인하고
// 아니라면 두 그룹을 합쳐준다.
// 이후 최종 root의 index값을 반환한다.
int make_net(int person1_idx, int person2_idx){
    int x,y;
    x = find_root(person1_idx);
    y = find_root(person2_idx);
    
    if(x != y){
        root[y] = x;
        networks[x] += networks[y];
    }
    return x;
    
}



int main(){
    
    int test_case;
    scanf("%d",&test_case);
    
    while(test_case){
        int F;
        scanf("%d",&F);
        
        map<string, int> friend_list;
        idx = 0;
        
        for(int i=0 ; i< maximum ; i++){
            networks[i]=0;
            root[i]=i;
        }
        
        for(int i=0 ; i< F; i++){
            char person1[21], person2[21];
            
            scanf("%s",person1);
            scanf("%s",person2);
            
            if(friend_list.count(person1) == 0){
                friend_list.insert(make_pair(person1,idx));
                root[idx] = idx;
                networks[idx] = 1;
                idx++;
            }
            
            if(friend_list.count(person2) == 0){
                friend_list.insert(make_pair(person2,idx));
                root[idx] = idx;
                networks[idx] = 1;
                idx++;
            }
            
            
            int r_idx;
            r_idx = make_net(friend_list.find(person1)->second, friend_list.find(person2)->second);// send person1&2's idx
            
            printf("%d\n",networks[r_idx]);
            
        }
        test_case--;
    }
    return 0;
}

 

※ map

 

<map> 헤더를 추가 후 사용 가능하다.

 

형식

map<key,value>

내용

count(key)                    // key값에 대한 value가 몇개있는지 반환
find(key)                     // map안에서 key값을 찾아 iterator를 반환
size()                        // map의 크기 반환
insert(make_pair(key, value)) // 추가
clear()                       // 맵의 모든 원소 삭제