별 찍기 - 10 [함수 / 6단계 / 2447번 / C# 풀이]

2447번: 별 찍기 - 10

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

첫째 줄에 N이 주어진다. N은 항상 3의 제곱꼴인 수이다. (3, 9, 27, ...) (N=3k, 1 ≤ k < 8)

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

 

규칙

문제는 예제를 보고 규칙을 유추해야합니다. N이 3, 9, 27일 경우를 가지고 별이 어떻게 그려질지 유추해보면 규칙이 보이긴 합니다. 이걸 식으로 만들어봐야합니다. 우선 복잡하니까... 3일 경우엔 식이 어떻게 될지 차근차근 생각해보겠습니다.

3

9

27

보면 규칙은 쉽게 찾을 수 있었습니다. 3개짜리는 가운데 구멍이 뚤린 그림이 나오고, 9개짜리는 3개짜리의 그림으로 둘러쌓여지고 가운데 구멍이 뚫리고, 27개도 마찬가지로 이어집니다.

 

여기까지는... 알겠는데... 도저히 문제를 풀 방법이 생각나지 않아 구글링을 했습니다.

 

일단 이 문제에서 필요한 알고리즘은 재귀알고리즘, 분할정복알고리즘 이었습니다. 재귀함수는 개념은 알고있었는데 사용해본적이 없었고, 분할정복알고리즘은 난생 처음 들어보는 개념이었습니다. 그리고 이러한 규칙성있는 기하학적 패턴을 프랙탈(Fractal)이라고한답니다.

 

자세한 설명은 아래의 두 링크가 친절하게 설명해주기 때문에 첨부합니다.

 

[2447번] 별찍기 10 - BOJ

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

코드

using System;
using System.Text;


class Program {

    static char[,] map = new char[3000, 3000];

    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        Init(n);
        FillStar(n, 0, 0);
        StringBuilder builder = new StringBuilder();

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                builder.Append(map[i, j]);
            }
            builder.Append("\n");
        }

        Console.WriteLine(builder.ToString());
    }

    //맵을 초기화 합니다. 입력된 n값에 맞게 초기화합니다.
    static void Init(int n)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                map[i, j] = ' ';
            }
        }
    }

    //별을 채웁니다.
    static void FillStar(int n, int x, int y)
    {   
        if(n==1)
        {
            map[x, y] = '*';
            return;
        }
        
        int div = n / 3;
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                if (i == 1 && j == 1)
                {
                    continue;
                }

                FillStar(div, x + (div * i), y + (div * j));
            }
        }

        return;
    }
}

코드를 한 번 써봤는데도 정확하게 이해가가지 않아서 추후에 복습 및 변형된 문제를 풀어봐야겠습니다.

 

콘솔출력

재귀함수때문에 멘탈이 흔들흔들거리네요