[P&B] #114 BAEKJOON 2447

공log/[P&B]

[P&B] #114 BAEKJOON 2447

ming_OoO 2023. 10. 12. 23:30

728x90

백준 2447번 JAVA 별 찍기 - 10

문제 설명

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

나의 문제 풀이 코드

import java.io.*;

public class bj2447 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        char[][] arr = new char[N][N];

        // 배열 초기화
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                arr[i][j] = ' ';
            }
        }

        drawStars(arr, N, 0, 0);

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sb.append(arr[i][j]);
            }
            sb.append('\n');
        }
        bw.write(sb.toString());
        bw.flush();
    }

    static void drawStars(char[][] arr, int N, int x, int y) {
        // Base case: N이 3일 때 별 찍기 패턴
        if (N == 3) {
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (i == 1 && j == 1) {
                        arr[x + i][y + j] = ' ';
                    } else {
                        arr[x + i][y + j] = '*';
                    }
                }
            }
            return;
        }

        int size = N / 3;

        // 3x3 영역을 재귀적으로 호출하여 별 찍기
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i == 1 && j == 1) {
                    for (int k = 0; k < size; k++) {
                        for (int l = 0; l < size; l++) {
                            arr[x + i * size + k][y + j * size + l] = ' ';
                        }
                    }
                } else {
                    drawStars(arr, size, x + i * size, y + j * size);
                }
            }
        }
    }
}

문제 풀이 코멘트

1. 배열 초기화

우선, 주어진 N에 따라 크기가 N×N인 배열을 만듭니다. 이 배열은 별을 찍는 공간입니다. 배열의 모든 요소는 공백으로 초기화됩니다.

2. 재귀 함수 drawStars
drawStars는 별을 찍는 주요 함수입니다.

Base Case (종료 조건): 입력된 N이 3일 때, 즉 가장 작은 패턴일 때, 별을 그리는 방법을 정의합니다. 3x3 정사각형 중 가운데 칸은 비워두고, 나머지 8개의 칸에 별을 채웁니다.
재귀적인 부분: N이 3보다 클 때, 크기 N의 패턴을 작은 패턴으로 나누어 그립니다. 크기 N의 패턴은 크기 N/3의 패턴으로 둘러싼 형태입니다. 이때, 크기 N/3의 패턴을 다시 drawStars 함수로 그립니다. 이 부분을 조금 더 자세히 설명해보겠습니다.

// 3x3 영역을 재귀적으로 호출하여 별 찍기
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        if (i == 1 && j == 1) {
            for (int k = 0; k < size; k++) {
                for (int l = 0; l < size; l++) {
                    arr[x + i * size + k][y + j * size + l] = ' ';
                }
            }
        } else {
            drawStars(arr, size, x + i * size, y + j * size);
        }
    }
}

재귀 함수 drawStars에서 가장 중요한 부분인 위의 코드는 큰 패턴을 작은 패턴으로 나누는 과정을 설명합니다. 이해를 돕기 위해 다음과 같이 설명하겠습니다.

for 반복문을 사용하여 3x3 크기의 작은 패턴을 순회합니다. 이 반복문은 i와 j를 사용하여 3x3 격자를 훑습니다.
중앙 칸(i=1, j=1)은 비워두어야 하므로, if (i == 1 && j == 1) 부분을 사용하여 중앙 칸에 공백을 넣어줍니다. 나머지 칸에는 별이 들어갑니다.
중앙 칸(i=1, j=1)을 제외한 나머지 칸(i, j)에 대해서는 else 부분을 통해 재귀 호출이 이루어집니다. 이것이 재귀의 핵심입니다. 재귀 호출은 작은 패턴을 그리는 drawStars 함수를 다시 호출하면서 크기를 N/3으로 줄입니다.
재귀 호출시에는 시작 위치를 x + i * size, y + j * size로 설정합니다. 이렇게 하면 큰 패턴을 3x3 작은 패턴으로 나누어 작은 패턴을 그릴 때 위치가 올바르게 계산됩니다.

이 과정을 통해 큰 패턴을 작은 패턴으로 나누고, 작은 패턴을 또 다시 나누어가며 별이 규칙대로 찍힙니다. 재귀 함수가 호출될 때마다 패턴의 크기가 작아지면서 작은 패턴을 그리고, 이 작은 패턴이 더 작은 패턴으로 나뉘어가면서 별이 찍힙니다. 이렇게 반복하여 큰 패턴을 구성하는 것이 재귀적인 접근 방식입니다.

3. 재귀 호출과 반복
drawStars 함수에서 3x3 크기의 작은 패턴을 그리는 부분은 반복문을 사용하여 처리됩니다. 중앙 칸은 비워두고 나머지 8개의 작은 패턴은 재귀적으로 그려집니다. 이 작은 패턴은 더 작은 패턴을 그릴 때도 동일한 방식으로 처리됩니다.
이러한 반복적인 재귀 호출을 통해 패턴이 계층적으로 그려지며, 가운데를 비우고 주변을 작은 패턴으로 둘러싸게 됩니다.

4. 결과 출력
모든 별을 그린 후, 결과 배열을 출력합니다. 별이 그려진 배열을 문자열로 변환하고, 줄 바꿈을 추가하여 표준 출력에 출력됩니다.

728x90