📌 구해야 하는 정답

여러 사람들에 대한 부모,자식 간의 관계가 주어집니다.

부모와 자식 관계면 1촌, 나와 부모의 형제들간의 관계는 3촌 등의 규칙으로 촌수가 계산됩니다.

주어진 두 사람의 촌수를 계산 하는 프로그램을 작성하는 문제입니다.

📌 풀이 하기

1️⃣ 두 사람의 촌수를 어떻게 계산 할 수 있을까?

입력 받은 가족 관계 정보를 그래프로 나타내보면, 어떤 두 사람의 촌수는 이어진 그래프 안에서의 깊이 차이 입니다.

입력받은 두 사람의 관계 중 누가 부모,자식인지 나와있지 않지만 괜찮습니다.

정보를 입력받을 때 그래프에 양방향 간선으로 입력을 받으면,

입력받은 두 사람 중 어떤 사람으로부터 탐색을 시작해도 깊이를 구할 수 있습니다.

DFS 탐색 구현하기

자 그러면 깊이를 구하는 dfs를 구현해보겠습니다.

dfs를 재귀함수로 구현할 때, 시작 지점 부터 몇단계 더 탐색했는지를 나타내는 count 값을 같이 탐색에 이용합니다.

어떤 노드와 연결된 다른 노드를 재귀로 탐색을 호출할 때 탐색 깊이를 나타내는 count값을 +1 하여 탐색해주면 됩니다.

그러면 연결되지 않은 경우(촌수를 구할 수 없는 경우)는 어떻게 구할 수 있을까요?