1167번 - 트리의 지름
게시글을 보니 두 번의 DFS를 이용하는 코드들이 대부분인데,
제가 문제를 풀 당시에는 두 번의 DFS를 사용한다는 것도 생각하지 못했고, 두 번 사용하더라도 정답이 될지 확신을 가지지 못했기 때문에 1번의 DFS만을 사용해 문제를 해결했습니다.
대단한 것은 아니지만, 저같이 1번의 DFS만으로 문제 해결 방향을 잡으신 분들에게 참고가 될까 하여 글 남깁니다.
1번만 DFS를 했을 때 문제점은, 트리의 지름 경로가, DFS를 시작하는 임의의 노드를 지나지 않는 경우, 지름을 구할 수 없는 것입니다.
그래서, 이를 보완하기 위해 각 노드를 루트로 하는 서브트리에서 지름이 존재하는지 확인하도록 했습니다.
각 노드를 루트로 하는 서브트리에서, 자신의 자식 노드로의 경로 중 길이가 가장 긴 것 2개를 더한 값을 answer과 비교해 업데이트했고, 이를 모든 서브트리에 대해 적용했습니다.
교수님 진도가 너무 빠릅니다..
댓글을 작성하려면 로그인해야 합니다.
yechan2468 1년 전 4
게시글을 보니 두 번의 DFS를 이용하는 코드들이 대부분인데,
제가 문제를 풀 당시에는 두 번의 DFS를 사용한다는 것도 생각하지 못했고, 두 번 사용하더라도 정답이 될지 확신을 가지지 못했기 때문에 1번의 DFS만을 사용해 문제를 해결했습니다.
대단한 것은 아니지만, 저같이 1번의 DFS만으로 문제 해결 방향을 잡으신 분들에게 참고가 될까 하여 글 남깁니다.
1번만 DFS를 했을 때 문제점은, 트리의 지름 경로가, DFS를 시작하는 임의의 노드를 지나지 않는 경우, 지름을 구할 수 없는 것입니다.
그래서, 이를 보완하기 위해 각 노드를 루트로 하는 서브트리에서 지름이 존재하는지 확인하도록 했습니다.
각 노드를 루트로 하는 서브트리에서, 자신의 자식 노드로의 경로 중 길이가 가장 긴 것 2개를 더한 값을 answer과 비교해 업데이트했고, 이를 모든 서브트리에 대해 적용했습니다.