만다라트 만들기
시간 제한1초메모리 제한1024 MB
9x9 만다라트 표를 입력받아 중간 목표 8개를 사전순으로 출력하고, 각 중간 목표 아래의 세부 목표 8개도 사전순으로 정렬해 출력합니다.
문제
우주는 만다라트를 활용하여 새해 계획표를 만들기로 했다.
만다라트는 3x3 행렬을 가로로 3개, 세로로 3개씩 배치해 9x9 행렬로 만든 표이다. 만다라트를 만들려면 먼저 아래와 같이 목표를 정해야 한다.
- 최종 목표를 1개 만든다.
- 최종 목표를 이루는 데 도움이 되는 중간 목표를 8개 만든다.
- 각각의 중간 목표를 이루는 데 도움이 되는 세부 목표를 8개씩 만든다.
이 목표들로 만다라트를 만드는 방법은 다음과 같다.
- 9x9 행렬을 3x3 행렬 9개로 구분한다.
- 9x9 행렬의 중앙에 위치한 3x3 행렬을 채운다. 최종 목표는 행렬의 가장 가운데에 쓰고, 중간 목표 8개는 나머지 8칸에 하나씩 쓴다.
- 중앙 3x3 행렬을 제외한 나머지 3x3 행렬의 가운데에 중간 목표를 다시 쓴다. 단, 중앙 3x3 행렬 안에서 중간 목표가 놓인 방향과, 9x9 행렬 안에서 같은 중간 목표가 쓰인 3x3 행렬이 놓이는 방향은 같아야 한다. 예를 들어 중앙 3x3 행렬에서 "건강"이라는 중간 목표를 최종 목표의 우상단에 썼다면, "건강"을 중심으로 하는 3x3 행렬은 9x9 행렬에서 우상단에 있어야 한다.
- 3x3 행렬의 빈칸을 세부 목표로 채운다. 가운데 쓰인 중간 목표를 이루는 데 도움이 되는 세부 목표 8개를 8칸에 하나씩 쓴다.
하지만 아무도 우주의 계획표를 알아보지 못했고, 우주는 만다라트를 쉽게 풀어 쓰기로 했다. 쉽게 쓴 계획표는 이렇게 만든다. 먼저 중간 목표를 하나 출력하고, 그 아래로 세부 목표 8개를 출력한다. 이를 8번 반복하여 중간 목표 8개와 그 아래의 세부 목표를 모두 출력한다. 이때 중간 목표끼리는 사전순으로 정렬되어 있어야 하며, 중간 목표 아래의 세부 목표 8개도 사전순으로 정렬되어 있어야 한다. 목표 a가 목표 b보다 사전순으로 앞에 오는 경우는 다음과 같다.
- 숫자가 알파벳보다 사전순으로 빠르다.
- 알파벳 대문자가 알파벳 소문자보다 사전순으로 빠르다.
- 길이가 i인 목표와 길이가 i+1인 목표가 있으며, 두 목표의 0번째부터 i번째 인덱스까지의 문자가 같으면 길이가 i인 목표가 사전순으로 빠르다. 예를 들어 목표 "ab"는 목표 "abc"보다 사전순으로 빠르다.
입력
9줄에 걸쳐 9x9 크기의 만다라트가 주어진다. 주어지는 만다라트는 모두 유효하며, 유효한 만다라트의 조건은 다음과 같다.
- 9x9 행렬의 중심 3x3 행렬에 최종 목표와 중간 목표가 있다.
- 중심 3x3 행렬에서 중간 목표가 쓰인 방향과 나머지 3x3 행렬에서 중간 목표가 쓰인 방향이 일치한다.
- 같은 목표는 두 번 주어지지 않는다. 단, 중간 목표는 행렬에서 총 2번씩 등장한다.
모든 목표는 영문 소문자, 대문자, 숫자로 구성되며, 길이는 각각 100을 넘지 않는다. 서로 다른 목표는 공백으로 구분되고, 한 목표 안에는 공백이 없다.
출력
1번째 줄에는 "#x. "를 출력한 다음, 사전순으로 가장 먼저 오는 중간 목표를 출력한다. 숫자가 알파벳보다 사전순으로 먼저 오고, 알파벳 대문자가 소문자보다 사전순으로 먼저 온다. 2번째 줄부터 아래 8줄에는 "#x-y. "를 출력한 다음, 사전순으로 정렬된 세부 목표를 순서대로 출력한다. 중간 목표 1줄과 세부 목표 8줄을 번갈아 출력하는 과정을 8번 반복한다. x와 y는 1부터 시작하여 하나씩 증가한다.
최종 목표는 출력하지 않는다.