트리 지름
-
(백준 1967번 트리 지름 C++) 라이님 블로그 대회 알고리즘 따라잡기 10) Tree 3 with gptPROGRAMMING/알고리즘 2024. 5. 1. 15:00
풀이가 감이 오질 않아 gpt에게 물어보고 나름 내 스타일대로 풀어보았다. 백준 1967번https://www.acmicpc.net/problem/1967 트리에서 가장 긴 거리를 구하는 문제인데, gpt는 2번의 dfs방법을 사용해서 풀었다.보고나니 당연하게 느껴졌지만, 처음에는 생각하지 못했다..ㅠ 우선 가장 긴 거리는 당연히! leaf에서 출발해서 leaf에서 끝날 것이다..!그렇다면 우선 root에서 시작에서 가장 멀리 있는 leaf를 찾은 다음( = farthestNode)farthestNode에서 다시 dfs를 통해 가장 멀리 있는 leaf를 찾으면 된다. 여기서 신박했던 점은 farthestNode와 maxDistance를 찾는 방법이다.dfs 매 실행마다 farthestNode와 max..