BOJ 트리의 지름2 [BOJ]1167번: 트리의 지름 문제: https://www.acmicpc.net/problem/1167 트리의 지름은 두 단계를 통해서 구할 수 있습니다. 1. 임의의 노드에서 가장 먼 노드 K 찾기 2. 노드 K에서 가장 먼 노드까지의 거리 D 구하기 그러면 D가 정답이 됩니다. 해당 문제는 노드 간 거리가 주어져 있으므로 다익스트라 연산을 두 번하면 해결할 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1167.java 2022. 4. 28. [BOJ]1167번: 트리의 지름 www.acmicpc.net/problem/1167 stonejjun님의 풀이(stonejjun.tistory.com/149)를 참고하여 해결하였습니다. 자세한 사항은 위 링크를 참고하시면 됩니다. 풀이를 요약하자면 1. 그래프(트리)를 만들면서 임의의 리프 노드 'A'를 하나 구합니다. 2. 'A'에서 DFS를 돌려서 'A'랑 가장 먼 거리의 노드인 'B'를 구합니다. - 노드 'B'는 무조건 트리 지름의 한 점입니다. 3. 'B'에서 다시 DFS를 돌려서 'B'와 가장 먼 거리의 노드인 C'를 구합니다. 4. 'B'와 'C'의 거리가 트리의 지름이 됩니다. 코드: github.com/cotchan/algorithm/blob/main/cpp/BOJ/BOJ1167.cc 2021. 3. 10. 이전 1 다음
