[BOJ] 2250번: 트리의 높이와 너비

https://www.acmicpc.net/problem/2250


우선 root를 구해야합니다. parent가 없는 node를 찾으면 그것이 root입니다. 이후에는 traversal을 수행하는데, preorder traversal을 하면 쉽게 각 노드의 x축 기준 위치를 구할 수 있습니다. 그리고 각 node의 depth는 inorder traversal로 구할 수 있습니다. 굳이 traversal을 2번 할 필요 없이 한 함수 내에서 잘 처리할 수 있습니다.


무려 8번의 제출 끝에 맞췄는데 


1. root가 1이 아닐 수 있습니다.


2. 각 줄 마다 노드의 번호 / 그 노드의 left child / 그 노드의 right child가 들어오는데 노드의 번호가 1 -> 2 -> 3 -> ... -> N 순서로 들어오지 않을 수 있습니다.


이 두 가지 사실을 몰라서 고생했습니다.


https://github.com/encrypted-def/BOJ/blob/master/2250.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 2515번: 전시장  (0) 2018.01.07
[BOJ] 2306번: 유전자  (0) 2018.01.07
[BOJ] 2300번: 기지국  (0) 2018.01.07
[BOJ] 1239번: 차트  (0) 2018.01.07
[BOJ] 1017번: 소수 쌍  (0) 2018.01.07
[BOJ] 1946번: 신입 사원  (0) 2018.01.07
  Comments