[백준] 2247_별찍기10 / 재귀

 

 

Gold

 

 

문제

 

재귀적인 패턴으로 별을 찍어 보자.

N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***
* *
***

 

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다.

 

 

입력

 

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다.

즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

 

 

출력

 

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

 

 

 

---

 

풀이

 

import java.util.*;

class Main {
    static String[][] arr ;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int N = sc.nextInt();
        arr = new String[N][N];

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                arr[i][j] = " ";
            }
        }
        
        func(0, 0, N);

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                sb.append(arr[i][j]);
            }
            sb.append("\n");
        }
        System.out.print(sb);
        sc.close();
    }
    public static void func(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) continue; // 가운데에 해당하는 부분은 비워둔다 
                func(x + i*(N/3), y + j*(N/3) , N/3); // 3*3 격자로 나누어 다시 재귀 수행
            }
        }
    }
}

 

 

재귀

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

 

주어진 정사작형을 3*3 으로 나누고, 가운데 부분에 해당하는 부분은 비워둔다 

 

 

해결방법

1. N을 입력받고, N*N크기의 2차원 배열을 만들어 배열의 모든 값을 스페이스로 초기화한다. 
2. 재귀함수를 구현한다.
   1. 주어진 정사각형을 3*3으로 나누고, 가운데 부분애 해당하는 부분은 비워둔다. 
   2. 가운데를 제외한 3*3으로 나누어진 부분은 다시 재귀호출한다. 
   3. N이 1이되면 더 이상 나눌 수 없으므로 해당 위치에 별을 찍는다. 

 

 

 

 

---

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