7291 : 재귀 트리 높이
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
루트 노드에서 가장 깊은 리프 노드까지의 높이(최장 경로 길이)를 재귀적으로 구하십시오.
트리의 루트 노드는 항상 1번입니다.
재귀 원리: 트리 높이 = 1 + max(각 자식 서브트리 높이)
[제약 조건]
• 입력되는 모든 수는 정수입니다.
트리의 루트 노드는 항상 1번입니다.
재귀 원리: 트리 높이 = 1 + max(각 자식 서브트리 높이)
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 트리 노드 수 $N$이 주어집니다. ($1 \le N \le 1{,}000$)
둘째 줄부터 부모-자식 관계가
둘째 줄부터 부모-자식 관계가
부모 자식 형식으로 주어집니다.출력 설명
루트 노드로부터 가장 깊은 리프 노드까지의 높이를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
1 2
1 3
2 4
2 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
자식 노드 목록을 딕셔너리로 구성한 후,
def height(node): return 1 + max((height(c) for c in children[node]), default=0)를 루트에서 호출합니다.