백준 2447, 별 찍기-10

문제

 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***
* *
***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

예제 입력 1 복사

27

예제 출력 1 복사

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

 보게 되면 3n을 한 변으로 하는 정사각형의 가운데를 n을 한변으로 하는 정사각형 모양으로 파내는 형태가 계속 반복되는 모양세를 보인다. 재귀함수를 사용하면 쉽게 풀 수 있는 문제이다. 개인적으로 재귀의 아이디어를 사용하기 위한 문제라기 보다는 배열에 좀 더 친숙해질 수 있는 연습을 위한 문제라는 느낌을 받았다. 다음과 같이 나는 코드를 구현하였다.

1. 3n이 한 변의 길이로 주어지고, 왼 쪽 위 꼭짓점의 좌표가 주어졌을 때 가운데 n을 한 변의 크기로 하는 정사각형을 뚫는 함수 구현(punch 함수)
2. punch 함수를 이용하여 전체 판에 (0,0) 꼭지점 부터 차례로 구멍을 뚫어 패턴을 만드는 재귀함수를 구현((max/3-> ... -> n -> ... ->3->1)이런 식으로 구멍을 뚫게 된다!!)

 다음은 실제 코드이다.

#include <iostream>

void init(int N, char** plat) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			plat[i][j] = '*';
		}
	}
}

void draw(int N, char** plat) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			std::cout << plat[i][j];
		}
		std::cout << '\n';
	}
}

void punch(int startX, int startY, int size, char** plat) {
	if (plat == nullptr) {
		return;
	}
	else if (size%3!=0) {
		return;
	}
	else if (size==3) {
		plat[startX+1][startY+1] = ' ';
		return;
	}
	else {
		int blankSize = size/3;
		for (int i = startX + blankSize; i < (startX + 2 * blankSize); i++) {
			for (int j = startY + blankSize; j < (startY + 2 * blankSize); j++) {
				plat[i][j] = ' ';
			}
		}
	}
}

void pattern(int size, char** plat, int platSize) {
	if (size%3!=0) {
		return;
	}
	else{
		
		for (int i = 0; i < platSize; i+=size) {
			for (int j = 0; j < platSize; j += size) {
				punch(i, j, size, plat);
			}
		}

		pattern(size/3, plat, platSize);
	}
}

int main() {
	int N;
	std::cin >> N;

	char** plat = (char**)malloc(sizeof(char*)*N);
	for (int i = 0; i < N; i++) {
		plat[i] = (char*)malloc(sizeof(char) * N);
	}

	init(N, plat);
	pattern(N, plat, N);
	draw(N, plat);

	for (int i = 0; i < N; i++) {
		free(plat[i]);
	}
	free(plat);

	return 0;
}

 

 개인적으로는 재귀의 아이디어를 체득하는 것도 그렇지만, 배열의 활용, 다이나믹 메모리 할당에 대해서 복습할 수 있어 좋았던 문제이다. 이것으로 글을 마친다.