210713 BOJ 1967 - 트리의 지름
- 트리모양을 잡아 당겨 일렬로 늘렸을 때 양 끝단의 거리가 가장 먼 거리를 구하는 문제
- 양 끝단: 루트 - 리프 or 리프 - 리프
- 리프 노드에서 리프 노드로 연결하기 위해서는 부모를 알아야하므로 양방향 셋팅 필요
- 나의 풀이
- 트리의 리프들을 찾아내고(해당 노드를 부모노드로 하는 노드가 있는지 여부)
- 리프노드 전부를 시작점으로 DFS를 돌면서 리프를 만나면 MAX값과 비교
- 실행시간: 2000ms
- 최적화
- 처음에 루트에서 리프를 dfs를 돌면 가장 루트에서부터 가장 긴 거리를 가진 리프를 알수있게 된다
- 그러니 이 리프 노드에서 dfs를 한번 더하게 되면 답임(-1800ms)
- 그리고 노드끼리 이어진 간선이 하나라서
- visit 말고 이전으로 돌아가지만 않도록 처리하면 된다(-10ms)
- 코드보기