백준 11671 1167. 트리의 지름 (Python) 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 트리의 지름을 구하려면 임의의 노드에서 가장 멀리 있는 노드 u를 구한다. 그 후 다시 노드 u에서 가장 멀리 있는 노드 v를 구한다. 이렇게 구한 노드 u와 노드 v의 길이가 트리의 지름이 된다. 이에 대한 증명은 링크를 참고하자... 코드 from collections import deque import sys input = sys.stdin.readline # node에서 가장 멀리 떨어져 있는 노드를 구하기 위한 bfs 함수 def .. 2022. 4. 11. 이전 1 다음
