문제

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

입출력 예

• 입력

  

• 출력

  

풀이

대표적인 재귀알고리즘을 사용하는 문제입니다. 별찍기 문제는 기본적이지만 숙련 코드에 대한 이해를 기반으로 풀어야 합니다. 일단 문제와 풀이된 코드를 확인하고 이후 설명하겠습니다.
입력의 경우 3의 거듭제곱 형태로 입력이 된다는 조건이 존재합니다. 이에 따라서 3이 입력되면 가로 3개 세로 3개의 별이 출력되는것을 볼 수 있습니다.
이 부분을 예외조건으로 설정해 준다면 문제를 쉽게 풀 수 있습니다.

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

void starpoint(int n, int x, int y)
{
    if ((x / n) % 3 == 1 && (y / n) % 3 == 1)
    {
        cout << ' ';
    }
    else
    {
        if (n / 3 == 0)
        {
            cout << '*';
        }
        else
        {
            starpoint(n / 3, x, y);
        }
    }
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            starpoint(n, i, j);
        }
        cout << '\n';
    }
    return 0;
}

코드해석

왜 starpoint의 매개변수를 3개로 했을까를 먼저 생각해보면, n은 입력의 크기를 설정할 수 있는 변수, x는 가로(x축), y는 세로(y축)으로 설정하기 위해 3개의 매개변수를 이용하였습니다.
이후 starpoint 함수에서 제약조건을 설정해 각각의 경우에서 space(공백)을 출력할지 아니면 별을 출력할지를 생각해 봅니다.

main 함수에서 n을 입력받고 n의 크기만큼 starpoint라는 함수에 n, i, j를 매개변수로 넘겨줍니다. 그리고 n번 각각 반복할 동안 \n을 이용해 위치를 설정합니다.

starpoint라는 함수에 넘어가게 되면 첫번째 if문 안에 두가지의 조건에 대해서 공백에 대해서 설정해주어야 합니다. if문 에는 x축을 n으로 나누고 이를 다시 3으로 나눈 나머지가 1일경우에 공백을 출력합니다(y의 경우도 동일). 이를 다시 생각해보면 main함수에서 만약 3이 입력된다면 i와 j는 0부터 2까지 증가하게 됩니다. 그리고 n은 3을 유지한채로 starpoint함수를 호출하게 됩니다. 이후 starpoint에 들어간 (3, 0, 0)은 if문을 타지 않고 else문의 n/3==0을 타 *을 출력하게 됩니다.
** 공백을 출력하는 부분이 재귀적인 부분이며 중요한 부분이라고 생각합니다! 3을 입력했을때 호출되는 함수는 다음과 같습니다.
1. 3입력
2. (3, 0, 0) (3, 0, 1) (3, 0, 2) (3, 1, 0) (3, 1, 1) (3, 1, 2) (3, 2, 0) (3, 2, 1) (3, 2, 2)

그럼 *이 출력되는 (3, 0, 0)과 ' '(공백)이 출력되는 (3, 1, 1)의 각각의 경우를 보겠습니다.

1. (3, 0, 0)인 경우에는 0을 3으로 나눈 나머지가 1이 될 수 없으니 첫번째 if문을 타지 않고 else로 넘어갑니다. 여기서 n이 3이니 n/3으로 나누었을때 1이 되며 그 다음 else문으로 넘어갑니다. 그리고 n은 3으로 나누어져 1이 되며 else문에 있는 starpoint(3/3, 0, 0)을 호출하게 됩니다! 다시 정리해보면
   첫 번째 (3, 0, 0) -> if문 안탐 else문으로 넘어옴 -> 다음 if문 안탐 else문으로 넘어옴 -> 다시 starpoint(1, 0, 0)을 호출함
   두 번쨰 (1, 0, 0) -> if문 안탐 else문으로 넘어감 -> 1/3은 0이됨(정수이므로) -> *을 출력

2. (3, 1, 1)인 경우 1을 3으로 나눈 나머지는 0.3이므로 0이 됩니다. 다음 else문으로 넘어갑니다. 여기서 n이 3이니 n/3은 1이 되며 *을 출력하지 않습니다. 이후 else문으로 들어가 starpoint(3/3, 1, 1)을 호출하게 됩니다! 이것도 다시 정리하겠습니다!
   첫 번째 (3, 1, 1) -> if문 안탐 else문으로 넘어옴 -> 다음 if문 안탐 else문으로 넘어옴 -> 다시 starpoint(1, 1, 1)을 호출함
   두 번째 (1, 1, 1) -> if문 1%3 == 1의 경우를 만족하여 ' '공백을 출력하게 됨

이렇게 해서 백준 문제를 풀어보았는데 저도 더 좋은 방법이 있나 다시한번 혼자 생각하면 정리해야겠습니다...