References
문제분석
트리의 노드가 인자로 주어질 때, 해당하는 트리의 깊이와 너비를 가진 정보를 리턴하는 함수를 구현하시오
일단, 깊이와 너비의 정보를 알아야 하니까, 가장먼저 떠올릴 수 있는 것은 ‘탐색’이다. 트리를 모두 다 돌아봐야 총 몇층인지, 층 마다 몇개의 노드가 있는지를 알 수 있을 것이다.
현재까지 알고있는 트리의 탐색 알고리즘으로는 BFS(너비 우선 탐색), DFS(깊이 우선 탐색) 이 있다. 무엇을 쓰는게 적당할까?
돌파구
우리가 앞선 글에서, BFS를 구현 할 때 unvisitedQueue 를 사용해서 층의 구분을 했었다. 층이 우선순위가 되도록, 자식들을 큐의 뒤에다 붙여주기만 하면 되었다. 층의 구분!? 그렇다 층만 구분한다면, while 문 한 번에 node 하나가 큐에서 나오니까, 카운팅을 해주면 되겠다!
여기까지는 좋다. 근데, 층의 구분은 어떻게 명확히 할건데? 위의 단락에서 이야기 한대로 while 이 돌 때마다 counting 을 해 주면, 모든 노드의 개수만 구할 수 있다. 즉, BFS 알고리즘만으로는 층의 구분을 할 수 없다. 무언가가 필요한 시점이다.
그 무언가는 바로 LEVEL FLAG 다. 말그대로 깃발을 꽂는다고 생각하면 좋다. BFS 알고리즘에서는 자동으로 층의 구분을 알려주지 않기 때문에, 우리가 그 안에 깃발을 꽂는 행위를 추가하면 어떻게 될까?
LEVEL 깃발을 만나면, 층의 구분이 생기도록 구현 해보자.
구현
BFS의 알고리즘에서 ‘LEVEL’ FLAG 만 추가하면 쉽게 구현할 수 있다.
위의 코드를 실행하고 나면 treeInfo 에는 levelWidth 함수의 리턴값으로 배열이 담길 것이다. 배열의 길이가 곧 트리의 깊이를 나타내고, 각 인덱스의 요소는 최상위 층부터 아래층까지의 너비를 나타낸다.
