1967

[python3] 백준 1967 풀이 (트리의 지름, DFS)

이 문제는 그림을 보면 이해가 빨라진다. 우리는 각 노드를 쫙 잡아당겼을때 길이가 가장 길어지도록 하는 길이를 찾아야 한다. 만약 오른쪽 그림이 가장 길게 잡아당겨진 형태라고 가정한다. 그럼 오른쪽에 회색 노드들 중에서 아무거나 잡고 DFS를 통해 가장 먼 노드를 찾으면 그건 무조건 파란색 노드가 된다. 신기하게도 어떤 노드를 택하던 가장 먼 노드를 찾으면 그건 파란색 노드가 되는것이다. 진짜 신기하다. 그렇게 파란색 노드를 하나 찾고, 이번에 찾은 파란색 노드로부터 가장 먼 길이를 찾으면 우리가 찾고자하는 트리의 길이가 된다...... 그럼 DFS를 단 2번만 하면 해결되는 문제이다. 그럼 DFS할 때 각 길이만 저장하면서 확인하면 되는 것이다. 1. DFS(1)로 파란색 노드하나 찾기 2. DFS(B..