티스토리 뷰
https://www.acmicpc.net/problem/2250
2250번: 트리의 높이와 너비
첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다.
www.acmicpc.net
각 트리 노드의 열 번호를 구하고, 레벨에 따라 저장한다. 그 후 레벨에 따라 열 번호의 최소, 최대 값을 구해 연산하면 전체 트리의 최대 너비를 구할 수 있다.
레벨에 따라 트리 노드의 열 번호를 저장 해야하기 때문에 Map 자료 구조를 사용해야한다.
그리고 아래 제시된 그림을 보면, 각 노드의 열 번호가 중위 순회에 따라 부여된다는 것을 알 수 있다. 따라서 트리를 중위 순회하고 순회 순서에 따라 열 번호를 저장한다.
Python
Java
728x90
'PS > 백준' 카테고리의 다른 글
| [백준] 12865 평범한 배낭 (0) | 2021.06.16 |
|---|---|
| [백준] 11000 강의실 배정 (0) | 2021.06.12 |
| [백준] 2263 트리 순회 (0) | 2021.06.01 |
| [백준] 18111 마인크래프트 (0) | 2021.04.15 |
| [백준] 1436 영화감독 숌 (0) | 2021.04.15 |
댓글