백준 4195. 친구 네트워크

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

4195번: 친구 네트워크

 

키워드는 두 가지다. 

해쉬맵, 유니온.

 

일단 이름이 문자열로 주어져서 머리 아플수 있는데 그냥 해쉬맵에 각 이름을 key로 value에 번호를 각각 부여해서 문자열은 생각하지 말고 번호로 생각한다.

 

이제 두 사람이 주어질때 두 노드가 주어진다고 생각하면 된다.

두 노드를 연결했을때 두 노드가 속한 그래프의 노드의 수를 구하면 되는 것인데, Union-Find 알고리즘을 쓰면 된다.

 

다른 Union-Find 알고리즘과 조금 다른점은 해당 노드가 속한 그래프의 노드의 갯수를 구해야 한다는 점인데,

i 노드가 속한 그래프의 총 노드의 갯수를 저장하는 cnt[] 배열을 만들어,

Union을 수행할때마다 부모 노드가 되는 노드에 cnt 값을 몰아주면 된다.

예를들어 노드1, 노드3을 union 하는 상황이고 노드1이 부모노드가 된다면 cnt[1] += cnt[3] 을 해주면 된다.

물론 이후 cnt[3] = 0이 되어야 한다. (나는 항상 노드의 인덱스 값이 작은 노드가 부모가 되도록 한다) 

 

Union-Find 알고리즘에서 만약 부모가 같다면 이미 같은 그래프에 속한 상황이다.

그럴 경우에는 Union 해줄필요 없이 부모노드의 cnt값을 출력해주면 된다.