[ Algorithm ] 백준 4195번 - 친구 네트워크

union find ( disjoint set ) 알고리즘을 알아보자.

문제 설명

백준 4195번 - 친구 네트워크는 아래와 같다.

• 문제 설명
• 입력값

해당 문제는, 각 테스트 케이스에서 매 줄마다 두 사람의 “친구”관계가 입력되고, 친구 관계가 입력될 때 마다, 두 친구가 속한 친구 네트워크 ( 해당 친구 네트워크에 속한 사람의 수) 를 출력하는 문제이다. 문제를 해결하기 위해선 입력된 사람들을 여러 그룹으로 나누어, 해당 사람이 어느 그룹에 속해 있는지 저장을 해야 한다.

이는 전형적인 union-find(disjoint-set) 자료구조를 이용하는 문제이다.

union-find(disjoint-set) 이란?

union-find 와 disjoint-set 은 알고리즘에서 흔히 동일하게 개념을 설명하는 명칭으로 사용된다.\

disjoint-set

서로 중복되지 않는 부분 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조

• 각 부분 집합들은 “상호배타적” 이다. - 즉 공통되는 부분이 없다
• 서로소 집합 자료구조

union-find

disjoint-set 자료구조를 표현하기 위해 지원해야 하는 연산들

union-find 의 연산

• union(x,y)
  • 원소 x 와 y 가 포함된 집합을 합치는 연산. 이미 동일한 집합에 속해 있을 경우 아무것도 하지 않음.
• find(x)
  • 원소 x 가 포함된 집합을 구하는 연산.

union-find 의 구현

union-find 는 집합을 표현하기 위해서 트리 구조를 쓰며, 해당 원소가 속한 트리의 root 번호가 해당 원소가 속한 집합의 번호가 된다.

초기화

각 배열의 부모노드 번호를 각 배열의 인덱스로 초기화 해 준다.

union 연산

두 노드의 루트노드를 하나의 트리로 합쳐 준다.

• union(1,3)

• union(3,4)

find 연산

노드가 속한 트리의 루트 노드를 반환한다.
배열 기준으로 부모노드 번호를 따라가며, 노드번호와 해당 부모노도의 번호가 동일할때까지 재귀적으로 올라간다.

• find(3)

문제 풀이

해당 문제는 입력으로 들어오는 사람의 이름을 map<string,int> 를 사용하여 < 이름 - 노드 > 번호 관계를 만들어 주고,
매긴 노드 번호를 기반으로, 새 친구 관계가 들어올 때 마다 union-find 연산을 해 주어,
합쳐진 트리에 속한 노드의 개수를 반환해 주면 되는 문제이다. - 노드 개수 카운트 최적화를 위해 size 배열을 따로 관리해 주었다.

풀이 전문은 아래와 같다.