3973 Time To Live (c++)

다른 문제들을 풀다 막힘이 생기면 쉽게 쉽게 알고리즘 분류를 켜고 정답 코드를 찾아봤던 것과는 다르게 이 문제는 처음부터 끝까지 혼자 고민하며 온전히 나 스스로 해결하게 될 것이다. 

 

문제 링크 : https://www.acmicpc.net/problem/3973

 

-- 문제 풀기 전에 했던 고민 --

실수 1

문제를 잘못 이해해 트리의 전체 TTL값을 최소로 하기 위한 방법을 고민하였다 

관찰 1

최대 TTL값은 항상 Leaf node에서 발생한다

  - Leaf node마다 bfs를 돌려서 마지막에 만나는 곳을 라우터로 하여 정답을 찾는다 (?)

 

-- 첫 다짐을 깨버리게 되었다.

 

정답 풀이

 

어느 한 지점에서나 bfs를 돌리면 마지막에 방문하게 되는 노드(이 노드는 무조건 leaf일 수 밖에 없음)는 길게 늘어뜨렸을 때의 양 끝점 중 하나임이 항상 보장된다......