https://www.acmicpc.net/problem/2644
Problem
부모 자식 관계인 사람들이 주어지고 부모 자식 관계를 1촌이라고 할 때, 주어진 두 사람의 관계는 몇 촌인지 계산하는 문제
Solution
2차원 배열 relation을 만들어서 행을 부모, 열을 자식이라고 생각하고 부모 자식 관계가 성립하는 칸에는 1을 저장해주었다.
주어진 두 사람 중 한 사람을 시작으로 촌수를 뜻하는 count 변수를 증가 시켜주면서 DFS 재귀함수를 이용했다.
또, 문제에서는 1번 사람 ~ n번 사람으로 나오는데 배열의 index로 따져 0 ~ n-1로 계산하는게 너무 헷갈릴 것 같아서 배열의 크기를 +1 해서 생성해주고 모든 index 값도 1부터 시작한다고 생각하고 코드를 짰다. (0행 전체와 0열 전체는 패딩 값이라고 생각)
<코드 설명>
#1. index 1부터 배열 끝까지 반복
#2. 주어진 두 사람 중 첫번째 사람(num)을 먼저 부모라고 생각하고 부모 자식 관계인 사람이 있으면
#3. 주어진 두 사람 중 두번째 사람이 맞는지 확인한다. 맞을 경우
#4. 프로그램을 종료 시키면 되므로 촌수(count)를 1 증가시킨 후 출력하고 exit()으로 프로그램으르 종료한다.
#5. 만약 두번째 사람이 아니였다면, 촌수는 -1로 바꾸어주고 (방문했다는 표시)
#6. 부모 자식 관계가 성립된 사람(i)과 촌수에 1을 더해준 값을 가지고 재귀 호출한다.
#7. 만약 주어진 두 사람 중 첫번째 사람(num)이 자식일 경우도 위(#1 ~ #6)와 동일하게 생각해준다.
#8. 주어진 두 사람 중 첫번째 사람을 함수의 매개변수로 전달해주며 시작한다.
만약 exit()으로 프로그램이 종료되지 않고, return 값 없이 다시 돌아오게 되면, None 값을 가지고 돌아온다.
solve 함수를 다 마치고 돌아왔다는 뜻은 exit()를 만나지 못했다는 뜻이고, 그 말인즉 두번째 사람을 못 만났다는 뜻이므로 -1(촌수가 없다)를 출력해준다.
Python Code
