백준 2250

2250번: 트리의 높이와 너비

 

1. 각 노드의 열은 왼쪽에 있는 노드들의 개수 + 1이다. 왼쪽 서브 트리에 속하는 노드의 개수와 왼쪽에 있지만 서브 트리에 속하지 않는 노드를 잘 파악해야 한다. 왼쪽 서브트리의 개수는 재귀를 이용하여 구하고 그 외의 노드는 따로 매개변수를 이용하여 전달하여야 한다.

 

2. 각 깊이의 가장 왼쪽 열과 가장 오른쪽 열을 파악하면 각 깊이의 최대 너비를 알 수 있다. 노드를 방문할 때마다 업데이트 해주고 마지막에 최대 너비와 그 깊이를 구하면 된다.

 

  문제를 풀긴 풀었는데 1번 부분 논리를 좀 더 깔금하게 정리할 수 없나 고민 중이다. 왼쪽에 있지만 왼쪽 서브트리에 없는 노드들을 재귀적으로 파악할 방법이 있으면 깔끔할 텐데.

 

- Source code link

github.com/Bibidi/Algorithms/blob/master/boj/boj%202250.cpp