[JAVA] baekjoon 2447 별 찍기-10

문제

https://www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

 

이 문제는 재귀로 생각하는 것도 어려웠지만

공백과 별 찍는 것을 어떻게 채워나가야할지 규칙을 찾는 것이 힘들었다.

이해한 것을 기반으로 글을 작성해보려한다.

 

 

나의 풀이 

입력으로 받는 N은 3의 거듭제곱(3, 9, 27, 81..)인데, 재귀적으로 패턴이 존재한다고 한다. 바로 아래와 같이 가운데 공간이 비어있는 패턴이다.

***
* *
***

키워서 9X9인 크기로 보면 아래와 같다.

여기서도 가운데 부분이 공백으로 비어있다. (패턴이 구분되도록 색을 군데군데 입혔다)

그리고 3X3 블럭이 9 - 공백 1  = 8개가 붙어있다.

 

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

그리고 27X27은 예제로 나와있다.

27X27에서는 위의 9X9 사이즈인 블럭이 9 - 공백 1 = 8개 붙어있다. 그리고 마찬가지로 가운데 칸에는 공백이 있다.

 

 

공백의 규칙은 4번째까지 별을 찍고, 5번째 별을 찍을 때 공백이 나타난다.

그리고 공백의 크기는 아래와 같은 패턴이 있다. 

3X3에서는 1X1 크기,

9X9에서는 3X3 크기,

27X27에서는 9X9 크기의 공백을 찍어야 한다.

 

 

이제 재귀에 대해 생각해봐야한다.

 

N의 크기로 된 전체 블럭은 N/3 X N/3 크기의 내부 블럭들로 이루어져있다고 언급했다.

그리고 반복문을 돌면서 그 블럭 사이즈만큼 건너 뛰면서 아래 패턴을 그린다고 생각하면 된다.

***

* *

***

결국 최종적으로 별은 N=1이 되었을 때 찍지만 재귀호출을 통해 size를 줄여나가는 것이다.

그리고 공백은 main에서 첫 호출을 제외하고 매 호출마다 찍는다. 즉, size=9, 3, 1일 때 모두 공백을 찍는다.

 

아래 그림에서 빨간 원, 파란 원, 검은 원으로 구분했고, 이 원들을 아래 각 bold된 문장으로 말할 수 있다.

N=27일 때, 9X9 블럭들의 점들을 방문하면서 공백일 때는 공백을 찍도록 호출을, 공백이 아닐 때는 별을 찍도록 호출한다.

그리고 N=9일 때, 3X3 블럭들의 점들을 방문하면서 똑같이 호출하고,

N=3일 때, 마찬가지로 점들을 방문하면서 공백일 때는 공백으로, 별일 때는 별로 호출한다.

 

N=1이 되면 더이상 쪼갤 수 없으므로 그때는 전달받은 위치값에 별을 찍고 반환한다. (isBlack가 true일 때는 공백 찍는다.)결국 별을 찍는 상황은 N=1이 됐을 때이다.

 

 

예제를 기반으로 호출하는 인자에 대해서만 표시하면 아래와 같다. 

빨간 원, 파란 원, 검은 원과 그때그때 Size, 그리고 그 Size 내에서 반복될 blockSize를 적어놓았다.

필자는 해당 문제가 이해하기 어려웠기 때문에 아래처럼 직접 적어보니 이해하기 수월했다. (이해가 될 때까지 적어보면 된다.)

 

size가 27일 때는 blockSize만큼 추가되면서 반복문을 돈다.  (아래)

(x, y, isBlank)

(0, 0, false)

(0, 9, false)

(0, 18, false)

(9, 0, false)

(9, 9, true)

(9,18, false)

(18, 0, false)

(18, 9, false)

(18, 18, false)

 

나머지 패턴은 아래 그림을 참고하자!

결국 별을 찍을 때는 3X3 크기에서 보이는 패턴으로 별을 채우는 것이다. 그리고 이것을 호출된 x,y만큼 진행하면 전체 N x N 크기가 완성된다.

 

 

코드 뜯어보기

main에서는 printStar(0, 0, N, false);를 호출한다.

0,0 에서 시작되고 사이즈로는 입력받은 N을 전달한다. 첫 지점은 공백 구간이 아니기 때문에 false를 전달한다.

 

 

printStar 메서드에서 첫번째로 해야할 일은 공백 체크이다.

공백 표시는 별 표시와 달리 매 재귀호출마다 해준다.

N=27이라 할 때 size는 27 -> 9 -> 3 -> 1이 되는데 

그때마다 5번째 별을 찍을 시점에 공백으로 채워야 한다. 그래서 그때 파라미터의 isBlack 인자를 true로 재귀호출한다.

그럼 해당 조건문이 실행될 수 있다.

공백의 크기는 size/3 X size/3 크기만큼 채워진다.

size가 27이라면 -> 9X9크기를 공백으로 채워야하므로, (x, y) 부터 Size 크기만큼까지 ' '를 입력한다. 그리고 리턴한다.

// 1. 빈 공간 : ' '만 채우고 리턴.
        if (isBlank) {
            for (int i=x; i<x+size; i++) {
                for (int j=y; j<y+size; j++) {
                    arr[i][j] = ' ';
                }
            }
            return;
        }

 

크기가 1일 때 별을 찍는 코드

만약 공백이 아니라는 호출이었다면, 해당 if문으로 넘어온다.

이 조건문은 크기가 1이 됐을 때 실행된다. 결국 재귀 호출을 계속 하다가 크기가 1이 됐을 때 더이상 쪼갤 수 없을 때 '*'을 찍으면서 재귀 호출된 함수들이 스택 식으로 실행되게 된다. 

// 2. '*' : size가 1일 때까지 재귀로 호출하다가 size가 1이 되면 그때 하나씩 '*' 찍으면서 리턴하여 재귀 스택이 줄어듦
        if (size == 1) {
            arr[x][y] = '*';
            return;
        }

 

 

블럭 크기만큼 반복하며 재귀호출하는 코드

만약 크기가 아직 1이 아니라면 해당 코드가 실행된다.

위에서 언급했듯 크기가 N일 때, N/3 X N/3 크기의 블럭들로 구성되어있다고 했었다.

그래서 blockSize를 따로 변수로 두고, (x, y)에서 (x+size, y+size)까지 그 크기만큼 더해가면서

호출한다. count라는 변수로 5번째 점을 찍는 시점에는 공백 인자를 true로 두고 호출한다.

	int blockSize = size /3;
        int count = 0;
        for (int i=x; i<x+size; i+=blockSize) {
            for (int j=y; j<y+size; j+= blockSize) {
                count++;
                printStar(i, j, blockSize, count == 5);
            }
        }

 

전체 코드

import java.util.Scanner;

public class Main {
    static char[][] arr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        arr = new char[N][N];
        printStar(0, 0, N, false);
        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");
        }
        System.out.println(sb);
    }

    private static void printStar(int x, int y, int size, boolean isBlank) {
        // 1. 빈 공간 : ' '만 채우고 리턴.
        if (isBlank) {
            for (int i=x; i<x+size; i++) {
                for (int j=y; j<y+size; j++) {
                    arr[i][j] = ' ';
                }
            }
            return;
            // size=9인 때
            // 9행 9,10,11,12,13,14,15,16,17열
            // 10행 9,10,11,12,13,14,15,16,17열
            //..
            // 17행 9,10,11,12,13,14,15,16,17열
        }

        // 2. '*' : size가 1일 때까지 재귀로 호출하다가 size가 1이 되면 그때 하나씩 '*' 찍으면서 리턴하여 재귀 스택이 줄어듦
        if (size == 1) {
            arr[x][y] = '*';
            return;
        }

        int blockSize = size /3;
        int count = 0;
        for (int i=x; i<x+size; i+=blockSize) {
            for (int j=y; j<y+size; j+= blockSize) {
                count++;
                printStar(i, j, blockSize, count == 5);
            }
        }
    }
}