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

문제

[C++] 백준 2447: 별 찍기 - 10 GOLD 5
https://www.acmicpc.net/problem/2447

 

---

 

접근 방법

백준 2447은 N(=3^k) × N 크기의 정사각형에 별 패턴을 출력하는 문제로,

큰 정사각형을 3×3으로 분할했을 때 아래 규칙을 따른다.

• 가운데 블록은 전부 공백
• 나머지 8개 블록은 같은 패턴을 재귀적으로 반복

재귀 호출 중 바로 출력하는 방식으로 도전했다가 실패하고,
https://sernan96.tistory.com/122를 참고해 2차원 벡터에 결과를 먼저 저장한 뒤, 마지막에 한 번에 출력하는 방식으로 구현했다.

 

상세 아이디어

1) 전체 배열 초기화

vect를 N × N 크기의 2차원 벡터로 선언하고, 초기값을 전부 ' '(공백)으로 설정한다.

이렇게 하면 재귀 과정에서는 별이 필요한 위치만 *로 채워주면 되고,
가운데 블록처럼 비워야 하는 영역은 따로 처리하지 않아도 된다.

 

2) 재귀 함수의 의미

star(i, j, n)은 (i, j)를 좌상단으로 하는 n×n 영역에 별 패턴을 채우는 함수다.

나눠진 해당 구역의 첫 부분을 (i,j)로 표시한다.

 

3) 기저 조건 (n == 3)

더 이상 분할할 수 없는 최소 단위이므로,

• 가운데 한 칸만 공백
• 나머지 8칸은 별

이 규칙에 따라 직접 3×3 패턴을 완성하고 재귀를 종료한다.

 

4) 재귀 분할 (n > 3)

N이 27인 경우, 현재 영역을 n/3 크기의 9개 블록으로 나눈 뒤 순회한다.

if (((y - (n / 3)) % n == 0) && (x - (n / 3)) % n == 0)

• 위 조건문 코드를 통해 현재 블록이 가운데 블록인지 판별하며,
  가운데 블록은 공백이어야 하므로 재귀 호출을 하지 않고 건너뛴다. (continue)
• 나머지 8개 블록에 대해서만 star(y, x, n/3)을 호출한다.

이 과정을 반복하면 문제에서 요구하는 별 패턴이 완성된다.

 

구현 시 주의할 점

• 재귀 단계에서 가운데 블록을 반드시 제외해야 한다. (continue)
• 가운데 블록은 아예 건너뛰기 때문에, 초기에 벡터를 ' '(공백)으로 초기화 시켜주어야 한다.

 

---

 

코드

#include <iostream>
#include <vector>
using namespace std;

vector<vector<char>> vect;

void star(int i, int j, int n)
{
	if (n == 3)
	{
		for (int y = i; y < i + 3; y++)
		{
			for (int x = j; x < j + 3; x++)
			{
				if (y == i + 1 && x == j + 1)
					vect[y][x] = ' ';
				else
					vect[y][x] = '*';
			}
		}
		return;
	}
	for (int y = i; y < i + n; y += n / 3)
	{
		for (int x = j; x < j + n; x += n / 3)
		{
			if (((y - (n / 3)) % n == 0) && (x - (n / 3)) % n == 0)
				continue;
			else
				star(y, x, n / 3);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n = 0;
	cin >> n;

	vect.resize(n + 1, vector<char>(n + 1, ' '));

	star(0, 0, n);

	for (int y = 0; y < n; y++)
	{
		for (int x = 0; x < n; x++)
		{
			cout << vect[y][x];
		}
		cout << '\n';
	}

	return 0;
}