촌수계산

---

title: “2644 - 촌수계산”
date: “2019-02-19”

category: “algorithm”

문제요약

1. 입력으로 노드간의 부모자식 관계가 들어온다.
2. 노드를 사람으로 봤을때 입력의 2번째 줄에 위치한 2개의 노드간의 촌수를 구하시오

접근법

문제 설명에도 나와있듯 촌수는 가족관계를 나타내는 우리나라의 독특한 문화다. (다른나라에도 있는지는 잘 모르겠다…) 부모 자식간에는 1촌이 형성된다. 나와 부모님은 1촌인 것이다. 나와 조부모님은 2촌이 된다. 나와 부모님이 1촌, 부모님과 조부모님이 1촌이 되기 때문에 더하면 2촌이 되는 것이다. 따라서 4촌의 경우 보통 부모님의 형제의 자녀를 나타낸다. 나와 부모님이 1촌, 부모님과 조부모님이 1촌, 조부모님과 부모님의 형제분들이 1촌, 부모님의 형제분들과 그 자녀들이 1촌 해서 총 4촌이 되는 것이다. 이는 트리로 나타내면 더 이해하기 쉬워진다.

이 문제에서 입력으로 주어지는 것은 위와 같은 트리이다. 위의 트리와 차이점은 위의 트리는 부모님, 조부모님 등 관계가 써져 있다면 입력으로는 그냥 숫자가 들어온다는 점이다.

입력으로 주어지는 트리에서 2개의 노드간 촌수를 구하기 위해서는 두 노드와 루트 노드사이에 공통으로 존재하는 노드중 가장 높이가 높은 노드와 2개 노드 각각의 높이의 차를 더한것과 같다. 위의 트리에서 나와 부모님의 형제간 촌수를 계산한다고 하면 공통으로 갖는 노드중 가장 높이가 높은 노드는 조부모님 노드이기 때문에 나와 조부모님의 높이 차인 2 와 부모님의 형제와 조부모님의 높이차인 1을 더한 3이된다. 즉 3촌이라는 뜻이 된다.

이제는 입력으로 주어진 2개의 노드에서 BFS를 하기만 하면 된다. 2개의 노드에서 부모노드 방향으로 탐색을 진행하며, 공통으로 등장하는 노드가 생겼을때 해당노드까지의 거리(높이)를 더해주면 촌수가 된다.

Source Code

소스코드 보러가기

• 아직 주석이 달려있지 않습니다.
• pseudocode 보다는 python 코드를 올릴 예정입니다.
• Code Review는 언제나 환영합니다 (코드를 더 깔끔하게, 효율적으로 만드는걸 도와주세요!)