개요

[링크] 백준 1992번: 쿼드트리

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

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

접근 방식

이 문제도 [링크]백준 1780번(종이의 개수) 와 유사하다.
1780번과 다른 점은 네 부분으로 나눈 후,
조사를 하고 괄호 표시를 하는 부분이 달라진 점이다.

처음엔 괄호 넣는 부분이 좀 애매했다.
생각 해보니 아예 모든 부분이 한 숫자로 이뤄져 있다면
괄호없이 0 또는 1로 출력하라는 문구가 있어서
재귀로 나뉘어질 때 출력하면 되겠구나 생각이 들었다.

뭔가 1780번이랑 다르게 해보고싶어서 2차원배열을
벡터를 이용하지않고 2차원 배열에 동적 할당을 하는 방식으로
구현했다.

코드

#include<iostream>
#include<vector>

using namespace std;

char** arr;									//int로 하면 111을 다먹어서 char형으로 해야함
void input(int& amount) {					
	cin >> amount;
	arr = new char* [amount];				//1780 번이랑 다르게 동적 할당으로 2차원 배열 구성
	for (int i = 0; i < amount; i++) {
		arr[i] = new char[amount];
	}
	for (int i = 0; i < amount; i++) {		//입력값받아서 저장
		for (int j = 0; j < amount; j++) {
			cin >> arr[i][j];
		}
	}
}
void solution(int x,int y, int length) {	//1780이랑 원리는 유사
	if (length == 0) return;				// length가 1일때 마지막이여야하므로 0들어올땐 return

	char temp = arr[x][y];					//배열의 첫값 저장
	for (int i = x; i < x + length; i++) {
		for (int j = y; j < y + length; j++) {
			if (arr[i][j] != temp) {		//첫값과 다르면 다른 값으로 이뤄진 사각형이므로 재귀 시작
				cout << "(";				//네개로 나눠질 시, ( 출력
				solution(x, y, length / 2);
				solution(x, y+length/2, length / 2);
				solution(x+length/2, y, length / 2);
				solution(x+length/2, y+length/2, length / 2);
				cout << ")";				//나눠진값들이 다시 병합되면 )출력
				return;
			}
		}
	}
	if (temp-'0' == 0) {					//temp값이 char형이므로 int형과 비교하려면 '0'빼야함
		cout << 0;
		return;
	}
	else
	{
		cout << 1;
		return;
	}



}

int main() {
	int amount = 0;
	input(amount);
	solution(0, 0, amount);
	delete[] arr;								//해제
}

문풀후생

적어놨지만 처음에 int형으로 구현했다가
들어온 숫자 전부를 배열 한 칸이 먹어버려서
char형으로 바꾼 후, temp값 0과 비교할 때
'0'을 빼줘서 정상적으로 비교할 수 있게 만들었다.