yky2798   9일 전

안녕하세요 트리의 지름 문제 질문 올립니다.

우선, 다른 트리의 지름 문제(1167번/ 루트가 1로 정해진 것 -> https://www.acmicpc.net/problem/1967) 는 푼 상태입니다.

[1167번]

부모에서 가장 멀리 있는 노드를 찾고, 가장 멀리 있는 노드를 부모로 해서 다시 제일 멀리 있는 노드를 찾는 방식으로 말입니다.

이 문제는 친절하게 루트가 주어져서 무난하게 풀었습니다.

[1] 그런데 여기서 좀 헤매고 있습니다. 이와 같은 문제에서는 '루트'를 어떻게 처리할 지 고민이 됩니다. 


[2] 각 지점별로 dfs 를 쭉쭉 돌아서 max 값을 구하고, 그 max 값들 중에서 최대값을 구하는게 이 문제의 본질인걸까요??



댓글을 작성하려면 로그인해야 합니다.