(백준/C++) 2447번_별 찍기 - 10

2447번: 별 찍기 - 10 (acmicpc.net) 문제는 분할 정복(divide and conquer)과 재귀(recursion)에 대한 문제입니다.

분할 정복이란, 큰 문제를 작은 문제로 나누고 그 결과를 조합해 원래 문제를 해결하는 방법입니다.

이 문제는 분할 정복 문제이므로 재귀적인 접근법과 함께 생각해야 합니다.

1. 기저 사례 설정 (Base case)

재귀 함수에서 가장 중요한 단계는 기저 사례를 설정하는 것입니다. 이 문제에서 기저 사례는 N=1일 때입니다. N이 1이면 별을 찍습니다.

기저 사례(Base case)란?

재귀 함수가 더 이상 자신을 호출하지 않고 값을 직접 반환하는 조건을 의미합니다.
즉, 재귀 호출을 중단하는 조건이며, 재귀 함수가 무한히 반복되는 것을 방지합니다.

2. 분할(Divide)

이제 분할 정복을 시작해 봅시다.

분할 정복은 크게 세 단계로 나눕니다. 분할, 정복, 병합입니다.

이 문제에서 분할 단계는 크기 N의 패턴을 9개의 크기 N/3 패턴으로 나누는 것입니다. 이때, 각 작은 패턴은 원래 패턴의 특정 위치에 있습니다.

이를 위해 재귀 함수는 크기 N과 시작 위치 (x, y)를 매개변수로 가져야 하고, 각각의 위치는 (x + dx * (N/3), y + dy * (N/3))입니다. 여기에서 dx와 dx는 현재 단계에서 또 다시 분할 될 작은 패턴의 x, y 위치입니다.

3. 정복(Conquer)

정복 단계에서는 분할한 각 작은 패턴을 처리합니다.

작은 패턴의 크기가 1인 경우에는 기저 사례에 해당하므로 해당 위치에 별을 찍습니다.

그렇지 않은 경우에는 재귀적으로 정복 단계를 수행합니다. 즉, 크기 N/3 패턴을 다시 분할하고, 분할한 패턴을 처리합니다.

중요한 점은, 작은 패턴 중에서 중앙에 위치한 패턴은 공백으로 처리한다는 것입니다. 이 부분이 이 문제의 핵심입니다.

4. 병합(Combine)

이 문제에서는 저는 병합 단계를 따로 처리하지 않았습니다.

왜냐하면 별을 2차원 vector로 저장하고, 각 작은 패턴을 독립적으로 처리하며 vector에 그때그때 저장했기 때문입니다.

따라서, 각 작은 패턴이 그려지는 위치는 분할 단계에서 이미 결정되었으므로, 좌표를 계산해서 2차원 vector에 저장하는 것으로 병합 단계를 대신 했습니다.

---

풀이

위의 접근법 대로 차례차례 풀어가면 필요한 요소는 대부분 완성 시킬 수 있을 것입니다.

여기에서 저는 별을 2차원 vector로 저장했습니다. 왜냐하면 분할 정복을 하면서 순서를 확신할 수 없었기 때문에, 확실한 좌표를 기준으로 그리도록 했습니다.

#include <iostream>
#include <vector>
using namespace std;
struct point
{
	int X = 0;
	int Y = 0;
};
void printStar(vector<vector<bool>>& arr, int N, point p)
{
	if(N == 1) // 기저사례 처리
	{
		arr[p.X][p.Y] = true;
		return;
	}

	N /= 3; //분할
	for(int y = 0; y < 3; y++)
	{
		for(int x = 0; x < 3; x++)
		{
			if (x != 1 || y != 1)
				printStar(arr, N, point{ p.X + x * N, p.Y + y * N }); //정복
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;

	vector<vector<bool>> pattern(N, vector<bool>(N, false));

	printStar(pattern, N, point{0, 0});

	for (auto& v : pattern)
	{
		for (auto b : v)
		{
			if (b) cout << '*';
			else cout << ' ';
		}
		cout << '\n';
	}
}