백준 2644: 촌수계산 (Swift)

 

각 자식의 부모는 하나만 주어진다고 하였으므로, 노드간의 거리를 구하면 되는 문제이다.

친척관계를 구해야하는 두 사람 딱 "한 쌍"이 미리 주어지기 때문에,

딱 그 둘 사이의 거리만 구하면 된다.

여러 쌍의 촌수를 구해야한다면, Floyd-Warshall알고리즘으로 "2차원 배열"에 촌수를 담아 구성할 수 있고,

한 사람에 대하여 다른 여러 사람들과의 촌수를 구해야한다면 "1차원 배열"에 촌수를 담아 구성할 수 있을 것이다.

여기서는 딱 한 쌍에 대해서만 구하면 되므로, dfs혹은 BFS로 풀이가 가능하다.

그래프 문제가 나오면  BFS에 손이 더 많이 갔기에, 이번에는 DFS로 풀이해보았다.

 

재귀함수를 돌리며,node번호와 함께 촌수( 그냥 cs라고 매개변수 이름을 대충 지었다...)를 보내주며

우리가 찾고자하는 node번호가 나왔을 때, cs를 전역변수 chonsu( 대충 지었다..) 에 저장해준다.

 

종료조건에서 return해주는 것은 꼭 잊지 말고 해주어야한다