Baekjoon 1167 트리의 지름 JAVA

https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

 

 

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%201167

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

 

 

해당 문제는 트리 정보가 주어졌을 때 트리의 정점 간 거리가 가장 먼값을 구하는 문제다.

​

처음에 dfs 하나를 이용해서 방문 체크로 확인하면 되겠다 생각했더니

값이 12 가 나왔고, 생각해 보니 dfs가 두 개 필요하다 생각했고,

​

문제를 고민하던 중 친구가 힌트를 던져줘서 생각해 보다가 해결할 수 있었다.

​

힌트 내용은 시작에서 끝까지 가고 나서 다시 끝에서 시작하면 된다였고,

​

테케를 그림으로 그려 생각해 보면 어느 정점에서 가정 먼 점을 가면 그 점은

해당 트리에서 가장 먼 점 2곳 중 하나인 것을 알게 되었고,

처음 dfs는 1에서 출발해서 가장 먼 곳을 찾도록 하여서 그 정점을 저장해 주었고

이후 dfs에서는 찾은 정점에서 시작해서 가장 먼 정점으로 가도록 해서

최종 값을 찾도록 하였다.