재귀함수를 이용한 dfs는 위험합니다. 대부분의 재귀함수는 10번 정도만 재귀를 해도 프로그램이 깨지거든요. 반복문을 이용해서 단일 함수로 구현하세요.

또, 32번 줄에서 path를 한 번에 1씩만 늘리시는데, path가 오토바이가 이동한 거리니까 (dep+1)-mcdep만큼 늘려야 할 것 같네요.

그리고, 이동할 때의 조건도 좀 잘못된 것 같네요. 기존 위치에서 d 거리만큼까지 던질 수 있고, 새 위치에서 d 거리까지 던질 수 있다면, 두 노드 사이의 거리는 d보다 크지 않을까요?

적으신 코드 기준으로, 이런 형태의 트리를 만나면 어떻게 될 지 한 번 생각해보세요. 힘이 2일 때, 답이 얼마여야 할 것 같나요?

들어주신 예를 입력으로 넣었을 때 답이 4로 출력이 잘 됩니다..ㅜㅜ

반례 찾아왔습니다.

감사합니다! 찾아주신 반례로 다시 생각해보겠습니다!

이 문제는 DFS로는 풀기 어려울 것 같아요. 가장 깊이 있는 리프 노드에서부터, preorder 순서로 탐색을 해야 하거든요. 루트 노드에서부터 탐색을 하면 깊이가 충분히 짧아서 탐색할 필요가 없는 리프노드까지도 가서 출력이 늘어날 수 있어요.

아, 위에 적은 댓글은 무시해주세요. 잘못 생각했네요. 관건은 모든 노드를 한 번씩 다 탐색하는 겁니다. 그리고 postOrder를 응용해보세요. 이러면 한 번의 DFS로도 가능하네요.

조언 감사합니다! 

일단 DFS 두 번으로 풀이하는 것은 성공했는데 한 번으로 줄이려니 어렵네요 ㅜㅜ 

천천히 고민해보도록 하겠습니다 댓글 감사드립니다!

한 번에 하는 코드를 만들었습니다. 제가 맞았을 때 공개로 제출해서 채점 결과에서 제 코드를 보실 수 있을 겁니다. 가장 아래의 주석 부분이 핵심입니다.

이하는 이 페이지에 오신 분들을 위해 적는 것입니다. 만약 제가 이곳과 다른 게시글에 적은 반례들이 다 통과되어도 틀린 것으로 나오실 경우, 한 번 노드들의 순서를 뒤섞어서 다시 시도해보세요. 만약 정상적인 코드라면 순서가 바뀌어도 상관 없이 정답처리가 될 것입니다.