우리는 명절날 친척집을 가게 되거나 친척방문을 받아들이면 간혹 엄마의 사촌, 아니면 외할아버지의 조카를 보는 등
되게 촌수 정리가 어려운 상황에 직면하게 된다. 그래서 촌수정리를 존나 쉽게 Tree로 구현하여 찾아가는 방법을 알아보자.
그러려면 우선 Tree의 기본 구조를 알아야한다.
Tree는 Graph의 일종이지만 Graph랑 달리 절대로 노드 간의 환형순환을 이루지 않는 형태이다.
환형형태를 이루지 않다보니 위 사진처럼 명백히 Root-Node가 존재하며 명백하게 '층'이라고 일컬어지는 layer가 존재한다.
그렇다면 지금 저 지도를 마치 친척간의 관계도라고 생각하고 B와 C의 관계를 생각해보자.
B와 C는 같은 Layer에 있으면서 parent-node가 같으므로 형제관계라 볼 수 있는데 형제관계는 2촌관계가 된다.
그런데 B에서 C를 어떠한 경로라고 생각하면 B에서 C를 가는 동안 B에서 A, A에서 C 이렇게 두 번 path를 지나가게 된다.
즉, 촌수 관계는 저 트리에서 서로 관계를 알고 싶은 노드 간의 최단탐색 간의 path의 갯수라고 할 수 있으며,
다르게 표현하면 저 트리에서 모든 연결된 node간의 거리는 1이라고 했을 때의 최단탐색 경로의 길이라고도 할 수 있다.
