[백준] 1992번 쿼드트리

문제

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다.  N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

영상을 압축한 결과를 출력한다.

 

처음에 이 문제를 접했을때, 줄단위로 생각했다.

하지만 아니였다.

이 문제의 핵심은 사각형이다.

이게 무슨 말이냐면

사각형 전체가 1이라면 1을 리턴하고

0이라면 0을 리턴한다.

근데 문제는 모든 사각형의 숫자가 다를 수 있다.

 

그럼 어떻게 해야할까?

전체가 1또는 0이 될때까지 잘라줘야 한다.

11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

예제를 보면 n이 8이다.

그렇기 때문에 상하좌우 이런식으로 4등분으로 나누면

1111  
1111
0001
0001

0000
0000
1100
1100

1111
1111
1111
1111

0000
0000
0011
0011

이렇게 4등분으로 나눌수 있다.

여기서 세번째를 주의해야한다. 바로 전부 1이라는 걸 알 수 있다.

 

그러면 위의 식대로하면

(? ? 1 ? ) 이된다.

?는 더 나눌 있다는 뜻이 된다.

그러면

((? ? ? ?)(? ? ? ?)1(? ? ? ?)) 이런식으로 나눌 수 있다.

답은 아니긴 하지만...

전부 1또는 0이 아니라면 나누고 또 나눠야 한다.

그러다 n=1이라면 현재 있는 값을 리턴 시켜주면 된다.

 

#include <bits/stdc++.h>
using namespace std;

int arr[64][64];

void split(int n,int x,int y) {
  if (n == 1) {
    cout << arr[x][y];
    return;
  }

  bool one = true, zero = true;

  for(int i = x;i<x+n;i++) {
    for(int j = y;j<y+n;j++) {
      if (arr[i][j] == 1) {
        zero = false;
      } else {
        one = false;
      }
    }
  }

  if (zero) {
    cout << 0;
  } else if (one) {
    cout << 1;
  } else {
    cout << "(";
    split(n/2,x,y);
    split(n/2,x,y+n/2);
    split(n/2,x+n/2,y);
    split(n/2,x+n/2,y+n/2);
    cout << ")";
  }
}
int main(void) {     
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL);

  int n;
  cin >> n;

  for(int i = 0; i<n;i++) {
    string s;
    cin >> s;
    for(int j = 0;j<n;j++) {
      arr[i][j] = s[j] - '0';
    }
  }

  split(n,0,0);

}

 

주의할점 1 :  one,zero가 초기값이 true인 이유는

만약, false로 두게 되면 번호를 확인할때 그 값이 나오면 true로 바꿔주는데..

그러면 0도 되고 1도 되는 이상한 현상이 발생한다.

 

주의할점 2 : 범위는 항상 0으로 시작하는것은 아니다.

 

주의할점 3 : 예제가 전부 붙어있다.

 

이 세개만 잘 지키면 이해하는데 어려움이 없을 것 같다.

#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
char pic[64][64];
int N;

bool isAll0(int x, int y, int sz) {
	for (int i = x; i < x + sz; i++) {
		for (int j = y; j < y + sz; j++) {
			if (pic[i][j] == '1')
				return false;
		}
	}
	return true;
}

bool isAll1(int x, int y, int sz) {
	for (int i = x; i < x + sz; i++) {
		for (int j = y; j < y + sz; j++) {
			if (pic[i][j] == '0')
				return false;
		}
	}
	return true;
}

string quadtree(int x, int y, int sz) {
	if (isAll0(x, y, sz))
		return "0";
	if (isAll1(x, y, sz))
		return "1";
	return "(" + quadtree(x, y, sz / 2) + quadtree(x, y + sz / 2, sz / 2) + quadtree(x + sz / 2, y, sz / 2) + quadtree(x + sz / 2, y + sz / 2, sz / 2) + ")";
}
int main(void) {
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%s", pic[i]);
	cout << quadtree(0, 0, N);
}