BOJ/1992 C/C++

쿼드트리

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stack>
#include <algorithm>

char arr[100][100];

int black_check(int n, int aa, int bb) {
	int flag = 0;
	for (int i = aa; i < aa + n; i++) {
		for (int j = bb; j < bb+n; j++) {
			if (arr[i][j] != '1') {// 검은색이 1임
				flag = 1;
			}
		}
	}
	if (flag == 1) {
		return 1; // black이 아닌 영역이 있음
	}
	else {
		return 0; // 모든 영역이 black(1)임
	}
}

int white_check(int n, int aa, int bb) {
	int flag = 0;
	for (int i = aa; i < aa + n; i++) {
		for (int j = bb; j < bb + n; j++) {
			if (arr[i][j] != '0') {// 
				flag = 1;
			}
		}
	}
	if (flag == 1) {
		return 1; 
	}
	else {
		return 0; 
	}
}

void quadtree(int n, int aa, int bb) {
	

	if (black_check(n, aa, bb) == 0) {
		printf("1");
	}
	else if (white_check(n, aa, bb) == 0) {
		printf("0");
	}
	else {
		int nn = n / 2;
		printf("(");
		quadtree(nn, aa, bb);
		quadtree(nn, aa, bb + nn);
		quadtree(nn, aa + nn, bb);
		quadtree(nn, aa + nn, bb + nn);
		printf(")");
	}
}


int main() {

	int n;
	scanf("%d", &n);

	
	for (int i = 1; i <= n; i++) {
		scanf("%s", &arr[i][1]); // 1행 부터 입력받기!
	}

	quadtree(n,1,1);
	
	return 0;
}

바로 앞 문제에 Z를 풀었어서 아이디어를 떠올리기는 매우 쉬웠으나 멍청티비한 실수로 시간을 너무 끌었다.

string을 저장할 때 0행이 아니라 1행부터 저장하고 싶으면.. &arr[i][1]로 해주었어야 되는데 그냥&arr[i]로 해버렸다ㅠ.

Z를 푸실 분들을 이 문제를 먼저 풀어보고 들어가는 것이 좋을듯.