[BOJ] C++ 2447 별 찍기 10 - 재귀 심화 문제, C++로 다차원 배열 초기화 시 주의사항

2447번: 별 찍기 - 10

예제

27

ans:
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

---

먼저 귀납적으로 생각해 보자.

n = 3^k라 하면 

k = 1일 때 패턴을 찍을 수 있다.

k = α 일 때 패턴을 찍을 수 있다고 가정하면 k = α + 1 일 때 패턴은 아래와 같다.

이를 바탕으로 함수 구조를 짜보자.

 

1. 함수 정의 void func(int n, int a, int b) : (a, b)에 n 크기의 패턴을 찍는 함수이다.

2. base condition : n == 3이면 3 크기의 패턴을 찍고 종료한다.

if (n == 3)
{
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (i != 1 || j != 1)
                star[a + i][b + j] = '*';
    return;
}

3. 재귀식

• n * n 크기의 정사각형을 9등분 했을 때 왼쪽 위부터 오른쪽 아래 순서로 1 ~ 9번 섹션이라 하자.
• 5번 섹션을 제외하고 n/3 크기의 패턴을 찍으면 된다.

함수의 구현은 끝났지만 구현 시 주의사항이 하나 있다. char star [2300][2300] = {' ', }; 이런 식으로 초기화하게 되면 각 행을 문자열로 초기화하므로 이상하게 작동한다. 이는 문자형 배열뿐 아니라 모든 다차원 배열에도 적용된다. 따라서 개별적으로 초기화하거나 fill() 함수를 이용하자!

 

또 내가 짠 코드에서 최적화할 수 있는 부분이 몇 개 있다. 재귀식 부분에서 for문을 사용할 수 있고 마지막 출력 부분도 아래와 같이 할 수 있다.

for (int i = 0; i < N; i++)
    {
        cout << star[i] << '\n';
    }

 

/** 재귀 2447 별 찍기 - 10 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

char star[2300][2300];

void func(int n, int a, int b)
{
    // (a, b)에 n 크기의 패턴을 찍는 함수이다.
    if (n == 3)
    {
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (i != 1 || j != 1)
                    star[a + i][b + j] = '*';
        return;
    }
    // 정사각형을 9등분 했을떄 왼쪽 위부터 오른쪽 아래 순서로 1 ~ 9 번 섹션
    func(n / 3, a, b);             // 1번 섹션
    func(n / 3, a + n / 3, b);     // 2번 섹션
    func(n / 3, a + n / 3 * 2, b); // 3번 섹션
    func(n / 3, a, b + n / 3);     // 4번 섹션
    // 5번 섹션 공백 출력
    func(n / 3, a + n / 3 * 2, b + n / 3);     // 6번 섹션
    func(n / 3, a, b + n / 3 * 2);             // 7번 섹션
    func(n / 3, a + n / 3, b + n / 3 * 2);     // 8번 섹션
    func(n / 3, a + n / 3 * 2, b + n / 3 * 2); // 9번 섹션
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    for (int i = 0; i < N; i++)
        fill(star[i], star[i] + N, ' ');
    func(N, 0, 0);

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cout << star[i][j];
        }
        cout << '\n';
    }
}