포화이진트리 한붓그리기 timer 1s memory 32MB

높이 N의 포화이진트리(Full Binary Tree)가 하나 있다.

포화이진트리(Full Binary Tree)란 이진트리이면서 서브트리까지 모두 빈 곳 없이 꽉찬 트리를 말한다.

다음은 높이 N=3인 포화 이진 트리의 모습이다.

세종이는 해당 트리에서 한붓그리기를 하려고 시도하는데, 한붓그리기는 아래와 같은 절차를 걸쳐 진행된다.

1. 아직 색칠이 되어있는 않은 임의의 노드를 선택한다.

2. 해당 노드를 색칠 한 후, 해당 노드로부터 간선으로 연결된 다른 노드로 이동한다.
   단, 이미 색칠이 완료된 노드로는 다시 지나갈 수 없다.

3. 아직 트리의 모든 노드가 색칠되어 있지 않다면 1번으로 다시 돌아가 다시 한붓그리기를 진행한다.

세종이가 한붓그리기를 시도하는 최소 횟수를 알아보자.