창 분할

Dotty 소프트웨어 회사는 저렴한 텍스트 기반 터미널에서 동작하는 소프트웨어를 만든다. 이 회사의 한 응용 프로그램에는 주 창(main window) 하나가 있고, 이 창은 여러 개의 하위 창(subwindow)으로 반복해서 나눌 수 있다. 일련의 창 분할이 끝난 뒤의 화면 배치 설명이 주어질 때, 그 설명과 일치하는 최소 크기의 창 격자를 그려라.

여기서는 창의 경계선에만 관심이 있으므로 창 내부의 칸은 모두 공백으로 남긴다. 더 이상 나뉘지 않은 창(나뉘지 않은 창)에는 서로 다른 대문자 하나가 라벨로 붙는다. 텍스트 터미널에서 창의 경계는 다음 문자로 그린다.

• 나뉘지 않은 각 창의 왼쪽 위 모서리에는 그 창의 대문자 라벨을 놓는다.
• 라벨이 없는 창의 모서리에는 별표 * 를 놓는다.
• 모서리가 아닌 위/아래 경계에는 붙임표 - 를 놓는다.
• 모서리가 아닌 좌/우 경계에는 세로줄 | 을 놓는다.

예를 들어, 처음에 라벨 M 하나뿐인 응용 창을 좌우 두 하위 창으로 나누며 라벨 R 을 추가하고, 다시 왼쪽 하위 창을 상하 두 하위 창으로 나누며 라벨 C 를 추가하면 아래의 Window 1 이 만들어진다.

모든 분할 형태는 문자로 이루어진 이진 트리로 나타낼 수 있다.

• 나뉘지 않은 직사각형 창은 대문자 라벨 하나를 가지며, 그 창의 트리는 그 라벨 하나로 이루어진다.
• 창은 좌/우 두 하위 창으로 나뉘거나 상/하 두 하위 창으로 나뉜다. 그에 대응하는 트리의 뿌리는 분할 경계 문자, 즉 좌/우 분할이면 세로줄 |, 상/하 분할이면 붙임표 - 이다. 좌/우 분할이면 뿌리의 왼쪽·오른쪽 부분트리가 각각 왼쪽·오른쪽 창이고, 상/하 분할이면 각각 위·아래 창이다.

트리는 전위 순회(preorder) 로 더 간결하게 나타낼 수 있다.

• 노드가 하나뿐인(글자 하나) 트리의 전위 순회는 그 글자이다.
• 왼쪽·오른쪽 부분트리를 가진 트리의 전위 순회는 뿌리 문자(- 또는 |) 다음에 왼쪽 부분트리의 전위 순회, 그다음 오른쪽 부분트리의 전위 순회를 이어 붙인 것이다.

아래의 Tree 1-4 는 Window 1-4 에 대응한다. Tree 4 는 Tree 2 와 Tree 3 을 포함한다. 이들의 전위 순회는 다음과 같다.

|-MCR
-|-ABC-D|E-FG
-P-|Q|RST
|-|-ABC-D|E-FG-P-|Q|RST

나뉘지 않은 각 창은 내부에 적어도 한 글자를 담을 공간이 있어야 하므로, 모든 분할 트리에는 최소 창 크기가 정해진다. Window 1-4 는 Tree 1-4 의 최소 크기 창이다. 최소 크기 창이라도 모든 나뉘지 않은 창이 글자 한 개만 담는 것은 아니다.

크기 계산에서는 창이 내부 영역과 그 사방을 감싸는 반 칸 두께의 경계를 포함한다고 생각하면 편하다. 그러면 창의 전체 크기는 내부 크기보다 가로·세로 각각 1 크다. 창은 내부에 적어도 한 칸이 필요하므로 최소 전체 크기는 $2 \times 2$ 이다. 이 정의에서 좌·우 하위 창의 너비 합은 이를 감싸는 창의 너비와 같고, 상·하 하위 창의 높이 합은 이를 감싸는 창의 높이와 같다.

감싸는 창을 늘려야 할 때, 하위 창들은 각자의 최소 크기에 비례하여 늘어난다. 분할 방향으로 늘어난 전체 크기를 $D$, 그 최소 크기(두 하위 창 최소 크기의 합)를 $d$, 두 하위 창의 최소 크기를 각각 $d_1$, $d_2$ 라 하자. 비례 배분하면 늘어난 크기는 $D_1 = d_1 \times (D/d)$, $D_2 = d_2 \times (D/d)$ 가 된다. 이 값이 정수가 아니면 언제나 위쪽 또는 왼쪽 하위 창을 다음 정수로 올림하므로 $D_1 = \lceil d_1 \times D / d \rceil$, $D_2 = D - D_1$ 이다. 감싸는 창의 최종 크기는 항상 그 하위 창들의 최종 크기보다 먼저 정해진다.

예를 들어 높이 $10$ 으로 늘어난 창이 최소 높이 $2$ 인 위 창과 최소 높이 $4$ 인 아래 창으로 나뉘면 $d = 6$ 이므로 $D_1 = 2 \times (10/6) = 3.33\ldots$ 은 $4$ 로 올림되고 $D_2 = 6$ 이 된다. 모든 가로 분할과 세로 분할을 서로 맞바꾸면 같은 규칙이 높이 대신 너비에 적용된다.

입력의 첫 줄에는 창 구조를 설명하는 전위 순회의 개수를 나타내는 정수 하나가 주어진다. 그다음 줄부터 각 전위 순회가 한 줄에 하나씩 주어진다. 각 전위 순회는 구분자 | 와 -, 그리고 1개 이상 26개 이하의 대문자로 이루어진다.

각 전위 순회에 대해, 먼저 그 전위 순회의 번호(1부터 시작)를 한 줄에 출력한 뒤, 그 순회가 나타내는 최소 크기의 창 격자를 출력한다. 일반적인 대회 출력 규칙과 달리 이 출력에서는 한 줄에 공백이 둘 이상 연속으로 나올 수 있다. 출력 격자의 행 수와 열 수는 모두 53 이하이다.