[BOJ #2447] 별 찍기 - 10

BOJ #2447, 별 찍기 - 10 문제입니다.

 

이전에 해 오던 별 찍기랑은 꽤 다른 문제입니다. 이 문제의 핵심은 재귀(recursion)입니다. 문제에서 재귀라는 단어가 언급되기도 하였으므로 재귀를 이해하고 있는 사람이라면 어렵지 않게 풀 수 있을 것이라고 생각합니다.

 

입력으로는 3의 거듭제곱 수(3, 9, 27, ...)가 주어집니다. 출력으로는 N * N 크기의 패턴을 출력해야 합니다. 패턴은 이렇습니다.

 

우선 N == 3인 경우엔 다음과 같이 출력합니다. 이것이 base case가 됩니다.

***
* *
***

N > 3인 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N / 3) * (N / 3) 정사각형을 크기 N / 3의 패턴으로 둘러싼 형태가 됩니다.

 

따라서 N == 27인 경우 다음과 같이 출력합니다. recursive case 중 하나가 되겠습니다.

***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

 

여기서 N의 입력 범위는 3 ^ 7 == 2187까지입니다. 따라서 2187 * 2187의 배열을 만들어 두고 그 위에 재귀적인 방식으로 그려나가면 되겠습니다.

 

base case와 recursive case를 모두 구분해 드렸으니 구현은 쉽게 할 수 있습니다.

 

1. 전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

void make(char matrix[10000][10000], int N, int x, int y) {
	if (N == 3) {
		matrix[x][y] = '*';
		matrix[x + 1][y] = '*';
		matrix[x + 2][y] = '*';
		matrix[x][y + 1] = '*';
		matrix[x + 2][y + 1] = '*';
		matrix[x][y + 2] = '*';
		matrix[x + 1][y + 2] = '*';
		matrix[x + 2][y + 2] = '*';
	}
	else {
		int k = N / 3;

		make(matrix, k, x, y);
		make(matrix, k, x + k, y);
		make(matrix, k, x + k + k, y);
		make(matrix, k, x, y + k);
		make(matrix, k, x + k + k, y + k);
		make(matrix, k, x, y + k + k);
		make(matrix, k, x + k, y + k + k);
		make(matrix, k, x + k + k, y + k + k);
	}
}

int main(void) {
	int N;
	scanf("%d", &N);

	char matrix[10000][10000];
	for (int i = 0; i < 10000; i++) {
		for (int j = 0; j < 10000; j++)
			matrix[i][j] = ' ';
	}
	
	make(matrix, N, 0, 0);
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			printf("%c", matrix[i][j]);
		printf("\n");
	}
	

	return 0;
}

matrix 배열을 10000 * 10000으로 잡았습니다만 2187 * 2187로 하는 것이 메모리 상 더 효율적이겠죠. 그러나 10000 * 10000으로 해도 char형이기 때문에 메모리를 그렇게 많이 잡아먹지 않습니다. 또 make 함수 안쪽이 살짝 더러운데, 이중 루프로 돌리고 공백 정사각형을 출력하는 인덱스(두 개의 반복 변수가 모두 중간값)일 때는 continue하는 방법으로 개선해도 좋습니다.