BOJ 6991 : 계통 트리

문제 링크 : https://www.acmicpc.net/problem/6991

 

그래프 이론 문제 중에서 꽤 잘 만들었다고 생각하는 문제.

트리가 주어졌을 때, 거리가 3 이내인 두 노드는 "계통 그래프" 에서 연결된다.

문제는 "계통 그래프" 가 주어졌을 때, 이 "계통 그래프"가 나오는 원래의 트리를 찾는 것이다.

 

핵심은 트리의 형제 노드들(sibling nodes)이다.

같은 부모를 공유하는 형제 노드는 그들끼리 완전 그래프를 이룬다.

형제들 중 어떤 두 노드를 잡아도 계통 그래프에서 연결된다는 것이다.

조금만 더 생각해보면, "자기 자신도 포함하는" 인접리스트를 구성했을 때 형제 노드들은 그 구성이 완전히 일치한다.

 

따라서, 우리는 인접리스트를 구성한 후 그 연결상태가 완전히 동일한 노드들끼리 묶어주고 부모를 하나 붙여주면 된다.

나같은 경우는 연결상태들을 해싱하여 비교하였고, Union - Find 알고리즘으로 묶어주었다.

 

이후는 간단하다.

다른 그룹끼리 연결됐다는 것은 그들의 부모끼리 연결됐다는 뜻이므로 부모끼리 연결하면 된다.