Informatica Online Judge

  4진 트리 [0961 / 03C1]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 268   Total Tried : 274


The Champion of this Problem (C++) : gs17036 - ms / 492byte
My Best Submission (C++) : N/A

[JKJeong 2014]

Background

4진트리(Quad Tree)는 2진트리(Binary Tree)와 마찬가지로 정보과학에서 많이 이용되는 자료구조 중 하나이다. 특히 데이터의 압축에 다양하게 응용되기도 한다.

주어진 0과 1로 구성된 크기가 2^k * 2^k 인 2차원 배열의 내용을 보기와 같은 문자열로 나타내는 프로그램을 작성하시오.

주어진 구간의 값이 모두 1이라면 "1",
주어진 구간의 값이 모두 0이라면 "0",
주어진 구간의 값이 0, 1이 모두 존재한다면 이를 다시 길이가 2^(k-1)인 구간으로 4등분하여 4구간으로 나누어 새로운 구간으로 탐색 (단, 나눈기 전에 "X"를 출력하여 현재 구간이 4개로 나눠짐을 표현.)

예를 들어 크기가 4*4이고 주어진 데이터가

0 0 1 1
0 0 1 1
1 0 0 1
0 0 0 1

이라면

처음 전체 구간이 0, 1이 모두 존재하므로 "X"를 출력하고 구간을 4개로 나눈다.
탐색순서는 원래 구간에서 다음과 같은 순서로 진행한다.

(1) (2)
(3) (4)

즉 원래 구간이 다음과 같이 4구간으로 나뉜다.

0 0
0 0

1 1
1 1

1 0
0 0

0 1
0 1

의 4구간으로 나눠 순서대로 탐색한다.

나눠진 구간 (1), (2)는 1과 0으로 더 이상 탐색이 필요없고 (3), (4)는 다시 4구간으로 나뉘어 마지막 까지 탐색한다.

따라서 위 행렬이 출력하는 최종결과는

X01X1000X0101

이 된다.

위 과정을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 한 변의 길이 n이 입력된다.
두 번째 줄부터 n줄에 걸쳐서 각 원소 가 입력된다.

[입력값의 정의역]
1 <= n <= 1024 (단, n은 2^k, 0 <= k <= 10 )
각 원소는 0, 1중 하나이다.

Output

탐색한 결과를 출력한다.

IO Example

입력
4
0 0 1 1
0 0 1 1
1 0 0 1
0 0 0 1

출력
X01X1000X0101

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]