[알고리즘 문제 풀기] 별 찍기 - 10(2447)

1. 문제 풀이 아이디어

• 재귀로 n×n 배열을 3×3 패턴으로 분할해 가운데를 제외한 영역에 별을 찍어 문제를 해결한다.

2. 나의 정답 코드

using System.Text;
StringBuilder sb = new StringBuilder("");

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int[,] pattern = { { 0, 0 }, { 0, 1 }, { 0, 2 }, { 1, 0 }, { 1, 2 }, { 2, 0 }, { 2, 1 }, { 2, 2 } };
    int n = int.Parse(sr.ReadLine());

    bool[,] star = new bool[n, n];

    solve(0, 0, n);

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            sb.Append(star[i, j] ? '*' : ' ');
        }
        sb.AppendLine();
    }
    sw.WriteLine(sb);

    void solve(int x, int y, int size)
    {
        if (size == 3)
        {
            for (int i = 0; i < pattern.GetLength(0); i++)
            {
                star[x + pattern[i, 0], y + pattern[i, 1]] = true;
            }
            return;
        }
        int ns = size / 3;
        for (int i = 0; i < pattern.GetLength(0); i++)
        {
            solve(x + pattern[i, 0] * ns, y + pattern[i, 1] * ns, ns);
        }
    }
}

3. 정리

• bool[,] 배열을 사용하여 별(*)의 위치를 저장한 후, 최종적으로 출력한다.

• 크기가 3이면 미리 정의한 패턴(pattern 배열)을 적용해 별을 찍고, 크기가 3보다 크면 9등분하여 가운데를 제외한 영역에 대해 재귀 호출한다.

• 재귀를 완료하면 star[i][j] 를 순환하여 값이 참일 경우 '*'를, 거짓일 경우 ' '를 추가하여 최종 문자열을 완성한 후 출력한다.