백준 2447 : 별찍기 - 10

허준기·2025년 3월 12일

알고리즘

목록 보기

13/14

이번주 알고리즘은 재귀 알고리즘이다

재귀는 개념적으로 그렇게 어려운게 없어서 바로 문제를 풀어보자

백준 2447 : 별찍기 - 10

별찍기

별찍기 주제에 무려 골드5 문제다!

그래도 별찍기니까 그렇게 어렵지는 않을것이라고 생각했다...

문제

재귀적인 패턴으로 별을 찍어보자. N이 3의 거듭제곱이라고 할 때, 크기 N의 패턴은 N x N 정사각형 모양이다.
가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.
N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3) x (N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태

입력

27

출력

***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

풀이

문제에 아예 재귀적으로 풀라고 나온다!
그래서 제일 작을 때의 문제부터 해결해봤다

for(int i = 0; i < 3; i++){
    for(int j = 0; j < 3; j++){
        if(i == 1 && j == 1){
            System.out.print(" ");
        } else {
            System.out.print("*");
        }
    }
    System.out.println();
}

위의 코드를 통해서 가장 작은 정사각형에 대해 그려줄 수 있었다

그럼 이제 더 큰 숫자가 들어왔을 때를 고려해야 한다.

처음에 생각한게 N이 3의 거듭제곱이니까 3으로 쪼개서 총 9개의 정사각형으로 이루어진 사각형을 재귀적으로 그려주면 된다고 생각했다.
사각형 한칸을 구한 후 계속해서 그려주는 방법을 생각했는데 한번 개행을 하면 돌아가기 어려워서 이차원 배열을 통해서 저장해주는 방식으로 변경하게 되었다.

그리고 만약 N이 3의 7제곱 같은 큰 수가 오게 되면 계속해서 그려주는 부분이 시간 초과가 날 수도 있다

package baekjun.recursion;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class P2447 {

    public static String[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = new String[n][n];

        recursive(n, 0, 0);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                sb.append(arr[i][j]);
            }
            sb.append("\n");
        }

        System.out.println(sb.toString());
    }

    private static void recursive(int n, int x, int y) {
        if (n == 3) {               // 제일 작은 사각형
            for (int i = 0; i < 9; i++) {   // 제일 작은 사각형의 크기만큼 반복
                if (i != 4) {       // 4가 가운데 -> 빈칸
                    arr[x + i / 3][y + n / 3 * i % 3] = "*";
                } else {
                    arr[x + i / 3][y + n / 3 * i % 3] = " ";
                }
            }
            return;
        }

        for (int i = 0; i < 9; i++) {
            if (i != 4) {   // 마찬가지로 빈칸이 아니면 재귀적으로 실행
                recursive(n / 3, x + n / 3 * (i / 3), y + n / 3 * (i % 3));
            } else {        // 빈칸이면 가운데 뻥 뚫림
                drawBlank(n / 3, x + n / 3 * (i / 3), y + n / 3 * (i % 3));
            }
        }
    }

    // 가운데 빈칸을 그려주는 함수
    private static void drawBlank(int n, int x, int y) {    
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[x + i][y + j] = " ";
            }
        }
    }
}