문제 풀이/백준 (BOJ)
[백준/BOJ] 1967번: 트리의 지름( diameter ) - C++ 문제 풀이
문제 설명 문제 링크: https://www.acmicpc.net/problem/1967 풀이이 문제는 주어진 트리에서 가장 긴 지름을 출력하는 문제입니다.여기서, 트리의 지름이란 트리에서 임의의 두 노드 사이의 경로의 길이를 말합니다. 우선, 가장 긴 지름을 얻을 수 있는 두 노드는 모두 리프 노드임을 알아야 합니다.리프( leaf ) 노드란 트리에서 가장 아래에 위치한 노드를 말합니다. 가장 간단한 트리를 가지고, 지름을 구하는 것부터 시작하겠습니다.그리고, 간선의 가중치는 1로 가정합니다. 위의 이미지에서, 가장 긴 지름은 2 노드에서 루트( root ) 노드를 지나, 3 노드 도달하는 경로의 길이라는 것을 알 수 있습니다. 이를 리프 노드 관점으로 다르게 표현하면,가장 긴 지름은 리프 노드에서..
2024. 6. 29.