1167 트리의 지름순

1.접근

모든 정점을 기준으로 DFS를 들어가보는 생각밖에 나지 않아서 풀어봤지만 시간초과가 났다(2≤V≤100,000)

도저히 생각나지 않았는데 트리의 지름을 구하는 쉬운 방법이 있었다.

2.풀이

트리의 지름을 구하려면 임의의 점을 잡고 그 점으로부터 최대거리를 가진 곳의 인덱스에서 다시 최대 거리를 구하면

그것이 지름이 된다.(처음 임의의 점에서 최대거리를 구할 때 트리의 지름과 겹치는 부분이 생길 수 밖에 없기 때문에 이라고 한다.) 따라서 DFS를 두번 써주면 된다 (임의의 점,임의의 점에서의 최대 거리 인덱스)

트리의 지름을 구하는 공식은 이곳에 자세히 있다.https://blog.myungwoo.kr/112

3.코드

4.배운점

• DFS나 재귀를 쓸때는 습관적으로 sys.setrecursion을 해주어야겠다 (런타임에러 방지)
• 트리의 지름 구하는 공식은 알아두자
• 입력 받을 때 순서대로 올꺼라고 생각하지말자(하루날림)