트리의 지름 썸네일형 리스트형 BOJ 8872 빌라봉 https://www.acmicpc.net/problem/8872 8872번: 빌라봉 첫째 줄에는 N, M, L이 주어진다. 둘째 줄부터 M개 줄에는 A[i] B[i] T[i]가 주어진다. 1 ≤ N ≤ 100,000 0 ≤ M ≤ N-1 0 ≤ A[i], B[i] ≤ N-1 1 ≤ T[i] ≤ 10,000 1 ≤ L ≤ 10,000 www.acmicpc.net 이 문제는 아래의 세 가지 경우로 나누어 생각할 수 있다. 1. Forest에 트리가 한 개인 경우 -> 그 트리의 지름 2. Forest에 트리가 두 개 이상인 경우 -> 그리디 해법: 반지름이 가장 큰 트리의 중심 정점에 다른 모든 트리의 중심 정점을 연결하는 게 최적이다. a. 반지름이 가장 큰 트리와 두 번째로 반지름이 큰 트리를 연결한 .. 더보기 이전 1 다음