[백준 1992번] 쿼드트리, 분할정복으로 해결하기

https://boj.kr/1992 

1992번: 쿼드트리

 

BOJ 1992 쿼드트리 솔루션

 

백준 1992번 쿼드트리 문제는 분할정복으로 해결할 수 있는 문제예요

한 번에 전체 사각형을 보기보다는, 어떤 사각형 하나를 처리하는 함수, 즉 부분 문제 하나의 솔루션을 작성하면

그 부분 문제들의 결과가 모여서 다시 최종 정답으로 도출되기 때문이에요

 

일반적인 풀이는 블로그에 많을 것 같아서

(별 이유는 없고 그냥) 전역변수를 사용하지 않는 코드를 작성해봤어요~

 

사각형 하나를 chk()로 검사한 후

전체가 같은 숫자로 채워져있으면 해당 숫자를 바로 정답 문자열에 추가해주고(zi 인덱스로 char z[]에 채워줍니다)

그렇지 않으면 괄호를 먼저 채워준 후, 각각의 사각형에 대한 결과(숫자 또는 (~)의 형태로 나오겠죠?)를 순서대로 채워줍니다.

 

참고로 아래 코드와 같이 이차원 배열인데, 파라미터를 배열로 안 받고 포인터로 받아버리면

작동은 하지만 incompatible type 경고가 발생합니다

 

#include <stdio.h>
#include <string.h>
#define L 64

int chk(char *b, int sr, int sc, int len) {
	char k = *(b + sr * L + sc);
	for (int i = 0; i < len; i++) {
		for (int j = 0; j < len; j++) {
			if (*(b + (sr + i) * L + sc + j) != k) {
				return 0;
			}
		}
	}
	return 1;
}

int f(char *b, int sr, int sc, int len, char *z, int zi) {
	if (chk(b, sr, sc, len)) {
		*(z + zi) = *(b + sr * L + sc);
		return 1;
	}
	int len_ = len >> 1;
	int zd = 0;
	z[zi] = '(';
	++zd;
	zd += f(b, sr, sc, len_, z, zi + zd);
	zd += f(b, sr, sc + len_, len_, z, zi + zd);
	zd += f(b, sr + len_, sc, len_, z, zi + zd);
	zd += f(b, sr + len_, sc + len_, len_, z, zi + zd);
	z[zi + zd] = ')';
	++zd;
	return zd;
}

int main(void) {
	int n;
	char b[L][L];
	char z[10000]; memset(z, 0, sizeof(z));
	scanf("%d", &n);
	getchar();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			b[i][j] = getchar();
		}
			getchar();
	}
	int zd = f(b, 0, 0, n, z, 0);
	printf("%s", z);
	return 0;
}