다익트스라1 [백준] 1167 트리의 지름 C++ 문제 풀이 접근 해당 문제를 풀기 위해서는트리와 그래프의 차이점트리에서 임의의 노드 i 를 잡아 가장 먼 거리에 위치한 노드 j 를 찾았을 때 j로부터 가장 길이가 먼 노드 k를 찾음으로 트리의 지름을 구할 수 있음들을 반드시 이해해야 합니다. 이해했다면 총 두 번의 탐색을 통해 트리의 지름을 구할 수 있음을 알 수 있습니다. (두 번의 탐색을 통해 트리의 지름을 구할 수 있다는 말을 이해하고 동의해야 합니다)대부분 인터넷에서 찾을 수 있는 풀이는 dfs로 풀지만 전 다익스트라를 통해 풀어보겠습니다. 풀이 과정 탐색하는 그래프가 트리임이 보장되므로, 절대 사이클을 가지지 않습니다.사이클을 가지지 않으므로 최소 거리 == 해당 노드로 가는 거리 입니다.해당 노드로 가는 최장 거리와 최소 거리는 동일합니다.따라서 가장.. 2024. 9. 22. 이전 1 다음
