백준 2644번: 촌수계산 (JAVA)

 

문제 해석

 

주어지는 두 사람 간의 촌수를 출력해야 한다. 둘 중 누구를 기준으로 촌수를 구하여도 같은 값이 나온다.

 

알고리즘

 

사람들간의 관계를 그래프로 구현하고 두 사람 중 한 사람으로부터 나머지 한 사람을 탐색하기까지의 깊이를 출력한다.

여기서는 BFS를 통해 탐색하였다.

깊이도 구해야하기 때문에 메모리 낭비를 줄이기 위해 방문 여부를 깊이 값으로 확인할 수 있도록 구현하였다.

두 사람의 관계가 이어져있다면 result에 원하는 결과값이 저장되도록 하고 아니면 그대로 -1을 출력한다.

 

코드