<递归> – <银1>
https://www.acmicpc.net/problem/1992
1992호: 쿼드트리
첫 번째 줄에는 이미지의 크기를 나타내는 숫자 N이 제공됩니다.
N은 항상 1 ≤ N ≤ 64 범위에서 2의 거듭제곱으로 제공됩니다.
두 번째 줄부터 길이가 N인 문자열 N개를 입력합니다.
각 문자열은 0 또는
www.acmicpc.net
( 1992 ) 쿼드트리
흑백 이미지를 압축하여 표현하기 위한 데이터 구조로 쿼드트리(quadtree)라는 방법이 있다.
하얀 점은 0, 검은 점은 1만 있는 이미지(2D 배열)에서 같은 번호의 많은 점이 한 곳에 집중되어 있으면 이를 압축하여 간단하게 쿼드트리로 표현할 수 있습니다.
주어진 이미지가 모두 0이면 압축 결과는 “0”이고, 모두 1이면 압축 결과는 “1”입니다.
0과 1이 섞이면 전체를 한 번에 표시할 수 없기 때문에 압축을 위해 4개의 이미지(좌상, 우상, 좌하, 우하)로 나누어 압축하고, 이 4개 영역의 압축 결과를 괄호 안에 표시한다.
주문 바인딩 및 익스프레스
위 이미지에서 왼쪽 이미지는 오른쪽 배열처럼 숫자가 할당되어 있는데 이 이미지를 쿼드트리 구조로 압축하면 “(0(0011)(0(0111)01 )1)” . N×N 크기의 이미지가 주어졌을 때 이미지를 압축한 결과를 출력하는 프로그램을 작성하세요.
::입력::
첫 번째 줄에는 이미지의 크기를 나타내는 숫자 N이 제공됩니다.
N은 항상 1 ≤ N ≤ 64 범위에서 2의 거듭제곱으로 제공됩니다.
두 번째 줄부터 길이가 N인 문자열 N개를 입력합니다.
각 문자열은 이미지의 각 지점을 나타내는 0 또는 1의 숫자로 구성됩니다.
:: 인쇄::
압축된 이미지의 결과를 출력합니다.
이것은 이전 두 질문과 정확히 동일한 논리를 사용합니다. 그러나 2차원 배열 형태로 연속 입력이 주어지면 0000으로 주어지면 한 줄씩 입력을 받아 따로 처리한다. 이 질문은 한 줄씩 입력을 받아 처리해야 하는데 그 부분 때문에 오류가 발생합니다. |
정답 코드
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int arr(65)(65);
bool check(int x, int y, int n) {
for (int i = x; i < x + n; i++) {
for (int j = y; j < y + n; j++) {
if (arr(x)(y) !
= arr(i)(j)) return false;
}
}
return true;
}
void solve(int x, int y, int n) {
// 답안 코드에는 해당 부분이 있었음 !
// 이게 틀린 원인일까봐 추가했는데 이 부분은 있어도 되고 없어도 됨
/*if (n == 1) {
cout << arr(x)(y);
return;
}*/
if (check(x, y, n) == true) {
cout << arr(x)(y);
return;
}
int k = n / 2;
cout << "(";
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
solve(x + k * i, y + k * j, k);
}
}
cout << ")";
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
string s;
cin >> s;
for (int j = 0; j < s.length(); j++) {
arr(i)(j) = s(j) - '0';
}
}
solve(0, 0, N);
return 0;
}