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

문제 바로가기

파이썬을 배우면 무조건 배운다는 별찍기 문제가 발전한 형태의 문제다.

재귀함수를 사용하는 유형인데, 아이디어를 생각하는데 조금 어려웠다.

3x3 블럭을 기준으로 어떻게 해보려고 했는데, 3x3 블럭 옆에 3x3 블럭을 놓는다는 개념을 구현하는게 불가능이었다.

3x3 블럭이 개행문자를 포함하고 있기 때문. 이 개행처리를 어떻게 해야할지 꽤 오랫동안 고민했다.

하지만 불가능하다고 판단하고, 다른 방법을 강구했다.

차라리, N * N 블럭에 모두 별표를 칠하고 빈 공간만 뚫기로 했다.

이 쪽이 훨씬 쉽고 또 옳은 풀이일거라고 판단했다.

 

블럭을 나타내는 배열 table과 한 변의 길이를 나타내는 변수 N을 전역변수로 선언했다.

블럭에 빈 공간을 뚫는 함수는 eidt으로, 인수로 대상이 되는 블럭의 한 변의 길이 K, 기준이 되는 좌표 (r, c)를 나타내는 pivot을 받는다.

char* table;
int N;

void edit(int K, pair<int, int> pivot) {
	if (K == 1)
		return;

	for (int r = K / 3; r < K * 2 / 3; r++)
		for (int c = K / 3; c < K * 2 / 3; c++)
			table[(pivot.first + r) * N + (pivot.second + c)] = ' ';

	for (int r = 0; r < K; r += K / 3)
		for (int c = 0; c < K; c += K / 3)
			if (r != K / 3 || c != K / 3)
				edit(K / 3, make_pair(pivot.first + r, pivot.second + c));
}

블럭의 크기가 1이면 할 게 없으니 return한다.

블럭의 행과 열의 위치가 모두 [1/3, 2/3)인 범위에서 빈 칸을 뚫어준다.

이를 마친 후, 블럭을 9등분을 한 뒤, 위 범위 외 블럭을 인수로 재귀호출을 해준다.

 

전체 코드와 243을 입력한 결과는 아래와 같다.

#define EL "\n"

#include <iostream>
#include <utility>

using namespace std;

char* table;
int N;

void edit(int K, pair<int, int> pivot) {
	if (K == 1)
		return;

	for (int r = K / 3; r < K * 2 / 3; r++)
		for (int c = K / 3; c < K * 2 / 3; c++)
			table[(pivot.first + r) * N + (pivot.second + c)] = ' ';

	for (int r = 0; r < K; r += K / 3)
		for (int c = 0; c < K; c += K / 3)
			if (r != K / 3 || c != K / 3)
				edit(K / 3, make_pair(pivot.first + r, pivot.second + c));
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N;

	table = new char[N * N];
	for (int i = 0; i < N * N; i++)
		table[i] = '*';

	edit(N, make_pair(0, 0));

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++)
			cout << table[y * N + x];
		cout << EL;
	}

	delete[] table;
	return 0;
}