(c++)백준 1992번: 쿼드트리

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

[풀이]

분할 정복으로 풀었다.

1. 현재 크기 n인 영상 안에 다른 숫자가 있는지 확인

2. 다른 숫자가 있으면 '(' 출력 후 n=n/4크기의 4개의 영상에 대해 1번 반복, 4개의 영상에 대한 재귀 끝나면 ')' 출력

3. 영상의 크기가 1이거나 영상 안에 다른 숫자가 없을 경우 영상안에 있는 숫자 출력 

 

※입력에 띄어쓰기가 없으므로 char배열에 한 글자씩 입력받거나 scanf("%1d",&video[i][j])를 써서 숫자 하나씩 입력받아야 한다.

 

#include <iostream>
#include <cstdio>//scanf
using namespace std;

int N;
int Video[64][64];

void getResult(int startx, int starty, int curSize) {
	//현재 영상의 범위 안에 다른 숫자가 있는지 확인
	for (int i = startx; i < startx + curSize; i++) {
		for (int j = starty; j < starty + curSize; j++) {
			//다른 숫자가 있으면 새로운 괄호 시작
			if (Video[startx][starty] != Video[i][j]) {
				cout << "(";
				for (int k = 0; k < 2; k++) {
					for (int l = 0; l < 2; l++) {
						//영상 크기가 1*1이면 그 숫자 출력
						if (curSize == 1) {
							cout << Video[startx][starty];
							return;
						}
						//4등분한 영상 각각의 시작하는 좌표와 크기를 인수로 재귀
						getResult(startx + (curSize / 2)*k, starty + (curSize / 2)*l, curSize / 2);
					}
				}
				cout << ")";
				return;
			}
		}
	}
	//영상 안에 다른 숫자가 없으면 그 숫자 출력
	cout << Video[startx][starty];
	return;
}

void solution() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			//입력되는 숫자 사이에 간격이 없으므로 scanf를 이용
			scanf("%1d",&Video[i][j]);
		}
	}
	getResult(0, 0, N);
}

int main() {
	solution();
	return 0;
}