[백준 2447번] 별 찍기 - 10 C++ 풀이

시간 제한

1초

메모리 제한

256MB

문제

재귀적인 패턴으로 별을 찍어 보자. 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번째 줄까지 별을 출력한다.

내 맞은 풀이**

#include<bits/stdc++.h>
using namespace std;
int N(0);
char board[2200][2200] = {};

// x가 행, y가 열
void blanks(int n, int x, int y) {
	if (n == 3) {
		board[x + 1][y + 1] = ' ';                    // 한 변이 3인 정사각형의 가운데 부분을 ' ' 를 이용하여 구멍을 뚫음
		return;
	}
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (i == 1 && j == 1) {                     // 한 변이 n일 때 가운데 부분을 ' '를 이용하여 구멍 뚫음
				for (int k = x + n / 3; k < x + 2 * (n / 3); k++) {
					for (int l = y + n / 3; l < y + 2 * (n / 3); l++) {
						board[k][l] = ' ';
					}
				}
			}
			else
				blanks(n / 3, x + i * (n / 3), y + j * (n / 3)); // 가운데가 아닌 경우 다시 n/3으로 다시 함수 부름
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N; 
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			board[i][j] = '*';
		}
	}
	blanks(N, 0, 0);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << board[i][j];
		}
		cout << "\n";
	}
}

어찌어찌 짜서 맞긴 했는데 위 코드는 뭔가.. 부족한 것 같다.
미리 *를 채워넣고 구멍을 뚫는 방식으로 했는데 심플하게 수렴할 수 있는 base condition을 찾는데에 실패하였다.
base condition에서 구현한 것을 함수에서 한 번 더 구현하였기 때문에 코드에 중복된 부분이 있다.
그래서 다른 고수분의 코드를 가져와보았다.

아래는 바킹독님 풀이

// https://blog.encrypted.gg/137
#include <stdio.h>
char map[2300][2300];
void solve(int N, int x, int y) {
	if (N == 1) {
		map[x][y] = '*';
		return;
	}
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (i == 1 && j == 1)
				continue;
			solve(N / 3, x + N / 3 * i, y + N / 3 * j);
		}
	}
}
int main(void) {
	int N;
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			map[i][j] = ' ';
	solve(N, 0, 0);
	for (int i = 0; i < N; i++)
		printf("%s\n", map[i]);
}

구멍을 뚫는게 아니라 *를 직접 그리는 방식으로 구현.
9개 영역으로 나누어 가운데 영역만 스킵하고 나머지는 재귀함수를 불러 base condition에서 ‘*‘을 그린다.
너무 깔끔하다