[백준] 2447: 별 찍기10

'2447- 별 찍기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이다.

예시 - 27

👉출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

예시 -

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

---

✍내 풀이

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
    	char[][] arr = new char[n][n];
        for (int i=0; i<n; i++) {
            Arrays.fill(arr[i], ' ');
        }
    	star(arr, 0, 0, n);
    	print(arr);
	}

    public static void star(char[][] arr,int startx, int starty, int n) {
    	if(n==1) {
    		arr[startx][starty] = '*';
    		return ;
    	}
    	
    	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);   
			}        		
		}    	
    	return ;
    }
   
    public static void print(char[][] arr) {
    	for(int i = 0 ; i < arr.length; i ++) {
    		System.out.println(arr[i]);
    	}
    }
}

---

✍Note

기본적인 재귀함수가 아닌 재귀함수를 처음봐서 문제를 푸는데에 어려움을 겪음ㅠ
몇시간동안 붙잡고 있다가 다른 분의 코드를 보고 이해하고 풀어낸 문제이다.

사용하는 기법은 분할정복 이다.

n이 27일 경우 27X27을 9X9짜리의 9개의 문제로 분할하고, 또 각 9개의 문제들을 3X3짜리 9개의 문제로 분할하는 것을 반복하여 처리하는 것이다.
( 27X27 -> 9X9 -> 3X3 -> 1X1 의 순서로 처리됨 )

이때 분할한 9개 문제들 중 가운데에 속해있는 부분은 재귀를 호출하지 않고
나머지 8개 부분의 경우는 가로 세로를 3으로 나누어 재귀를 호출한다.

재귀함수에서 빠져나가기 위한 base case는 n이 1일 경우이고 해당 위치에 * 을 저장한다.