12896번 - 스크루지 민호
저의 아이디어는 다음과 같습니다.1. 리프노드들을 찾아서 큐에 넣어서 제거하고(방문처리) 이후 리프노드와 연결된 노드들을 큐에 넣음으로써 계속해서 반복해서 중심을 찾는 것 2. 마지막에 하나만 남는경우와 여러개가 남는경우 거리가 달라져서 처리까지 완료ex) 1-2-3-4-5(마지막 한개 남음) , 1-2-3-4-5-6 (마지막 두개 남음)
뭐가 틀린 것인지 잘 모르겠습니다ㅠㅠ 반례 찾아주세여
두 노드 사이의 최대 거리는 5입니다. (1->2->4->6->7->9)따라서 답은 3이 됩니다.
하지만 적어주신 코드는 답이 2입니다.
테스트하시기 편하게 텍스트로 다시 적어드립니다.
이 문제에서 요구하는 것을 간단히 적으면 다음과 같습니다.
트리의 지름을 구한 후, 트리의 중심으로부터 가장 멀리 떨어진 노드까지의 거리를 출력하라.
감사합니다!
댓글을 작성하려면 로그인해야 합니다.
wwweric12 1년 전
저의 아이디어는 다음과 같습니다.
1. 리프노드들을 찾아서 큐에 넣어서 제거하고(방문처리) 이후 리프노드와 연결된 노드들을 큐에 넣음으로써 계속해서 반복해서 중심을 찾는 것
2. 마지막에 하나만 남는경우와 여러개가 남는경우 거리가 달라져서 처리까지 완료
ex) 1-2-3-4-5(마지막 한개 남음) , 1-2-3-4-5-6 (마지막 두개 남음)
뭐가 틀린 것인지 잘 모르겠습니다ㅠㅠ 반례 찾아주세여