백준 2447번 : 별 찍기 - 10 (JAVA) 문제 풀이

🚀문제

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

💬 예제 입력           

27

💬 예제 출력

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

 

 

🌈 나의 풀이

먼저 처음 별의 패턴을 찾아 보도록 하자.

 

 

가로 세로가 9이고, 가운데가 비어있는 9X9 별의 패턴이 계속 반복되는 패턴이다.

 

이 패턴을 다시 한번 분할 해보면..

이렇게 가운데가 비어있는 3X3 패턴이 반복이 된다.

 

인덱스를 표시해보면, 

27X27  패턴의 인덱스

 

9X9 -> 3X3 으로 분할된 모습

 

분할된 패턴의 인덱스를 나열해보면 ,  (0,0) 으로 시작하는 길이가 27인 별의 패턴이 다음과 같이 분할이 된다.

길이가 27이고 (0,0)으로 시작하는 별의 패턴이 다음과 같이 분할이 된다.

1)startX: 0 , startY: 0 , len: 9

2)startX: 0 , startY: 9 , len: 9

3)startX: 0 , startY: 18 , len: 9

 

4)startX: 9 , startY: 0 , len: 9

5)startX: 9 , startY: 9 , len: 9

6)startX: 9 , startY: 18 , len: 9

 

7)startX: 18 , startY: 0 , len: 9

8)startX: 18 , startY: 9 , len: 9

9)startX: 18 , startY: 18 , len: 9

이렇게 총 9개로 분할이 된다. 

여기서 또 길이가 9인 패턴을 길이가 3인 패턴으로 분할 시킬 수 있다.

길이가 3인 패턴으로 분할시키면 다음과 같이 된다.

1)startX: 0 , startY: 0 , len: 3

2)startX: 0 , startY: 3 , len: 3

3)startX: 0 , startY: 6 , len: 3

 

4)startX: 3 , startY: 0 , len: 3

5)startX: 3 , startY: 3 , len: 3

6)startX: 3 , startY: 6 , len: 3

 

7)startX: 6 , startY: 0 , len: 3

8)startX: 6 , startY: 3 , len: 3

9)startX: 6 , startY: 6 , len: 3

...
..
81)startX: 24 , startY: 24 , len: 3

이렇게 총 81개가 나오게 된다.

 

위에 그림을 보게 되면 조건 두가지가 보인다.

조건1) 재귀 호출 되는 부분의 N은 N / 3이 된다.

조건2) startX : 0*N , 1*N , 2*N ... 이렇게 호출이 된다.

 

이 부분을 구현 해보면

for(int i=0; i<3; i++){
	for(int j=0; j<3; j++){
 		star(arr, startX + i*(N/3) , startY + j*(N/3) , N/3)   
    }
}

이런식으로 호출 해주면 되고

 

재귀 메소드에 파라미터값으로 (배열의 주소값, 시작점x좌표, 시작점y좌표, 길이) 를 넘겨주면 된다.

이런식으로 계속 재귀 호출을 하게 되면 ? 종료 조건을 설정 해줘야 한다. 

N == 1 이 될 때까지 계속 재귀 호출을 해주고, N == 1인 경우에 *을 넣어주면 되는데, 

이때 주의 해야 할 점은, 가운데 부분은 별을 채우면 안되기 때문에, 반복문에서 i == 1 && j == 1 인 경우에 호출을 하지 않도록 설정 해주면 된다!

private static void star(int[] arr, int startX, int startY, int N){
	if( N == 1 ) {
    	arr[startX, startY] = "*"; // 1. 별을 넣어주고 
        return ; // 2. 종료
    }
    
    for(int i=0; i<3; i++){
    	for(int j=0; j<3; j++){
        	if( !(i==1 && j==1) ){
     			star(arr, startX + i*(N/3) , startY + j*(N/3) , N/3); 
            }
        }
    }
   
}

 

 

 

 

🛴전체 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        String[][] arr;
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(bf.readLine());
        arr = new String[N][N];
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                arr[i][j] = " ";
            }
        }
        star(arr, 0, 0, N);

        for (String[] strings : arr) {
            for (String string : strings) {
                bw.write(string + "");
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
    }

    public static void star(String[][] arr, int x, int y, int N) {
        if (N == 1) {
            arr[x][y] = "*";
            return; // 종료
        }

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (!(i == 1 && j == 1)) {
                    star(arr, x + i * (N / 3), y + j * (N / 3), N / 3);
                }
            }
        }
    }
}