백준 13016 내 왼손에는 흑염룡이 잠들어 있다 (1) 썸네일형 리스트형 백준 13016 내 왼손에는 흑염룡이 잠들어 있다 트리의 간선에 가중치가 있을 때 각 노드별로 가장 먼 노드를 찾는 문제입니다. 최대 50,000개의 노드에 대해 답을 구해야 하기 때문에 노드별로 DFS를 수행할 경우 시간초과를 피할 길이 없습니다. 따라서 트리의 지름을 구하는 알고리즘을 이용하여 아래와 같이 해결책을 찾을 수 있습니다. (dfs 3번 수행) 1. 먼저 임의의 특정 노드에서 가장 먼 노드를 찾음. (V: 트리지름의 한쪽 노드) 2. V에서 가장 먼 노드(U: 트리지름의 다른쪽 노드)를 찾으면서 V-->각 노드간 거리를 구함 3. U-->각 노드 간 거리를 구함. 4. 각 노드별 위 2,3에서 구한 값 중 큰 것이 가장 먼 노드가 됨. 1. 임의의 노드 1번에서 가장 먼 노드를 찾습니다. - 5번(거리 16, 트리 지름의 한쪽 끝) 2. .. 이전 1 다음
