Algorithm/백준 (1) 썸네일형 리스트형 [파이썬, python] 백준 1967 - 트리의 지름 트리의 지름 문제 dp를 사용해서 문제를 풀었는데 다른 사람들은 bfs를 사용해 풀어 정리하게 되었다. 트리의 지름에 대한 개념이 있어야 풀 수 있는 문제인 것 같다. 핵심 아이디어: 트리에선, 임의의 노드에서 가장 먼 점이 가장 거리가 먼 두 점(지름의 양 끝) 중 하나의 점 많은 사람들이 푼 방식은 bfs를 두번 사용해주는 것이었다. 1. bfs를 통해 임의의 노드로부터 가장 먼 노드A를 구해준다. => 이때의 노드 A는 트리 지름의 한 점이 된다. 2. bfs를 통해 노드A로부터 가장 먼 노드B를 구해준다. => 이때의 노드 B는 트리의 나머지 한 점이 된다. 중요한 아이디어는 1번의 " 임의의 노드에서 가장 먼 점이 가장 거리가 먼 두 점 중 하나의 점"이라는 것이다. 이에 대해 귀류법으로 증명한.. 이전 1 다음