[백준] 2447번 Java (재귀, 분할정복)

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

💡문제

풀이

접근법 : 큰 별 네모에서 가운데 네모를 뺀다.

사분면으로 나눠서 풀었던 z문제와 비슷하다. 접근법만 생각하면 쉬운 문제였다.

• 3*3의 배열이라고 생각하고 가운데 부분을 빼준다.
• 이제 나머지 8개의 작은 네모들을 기준으로 재귀적으로 가운데 빈칸을 만들어준다.
• 그렇게 크기가 한 변이 3*인 작은 네모가 될 때까지 반복한다.

내 코드

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

public class Main {
    static int n;
    static char [][] 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 char[n][n];	
        for (int i = 0; i < n ;i++) {
            Arrays.fill(arr[i], '*');
        }

        func(n, 0, 0);	// func(한 변의 크기, x좌표, y좌표)
        
        for (int i = 0; i < n; i++) {
            System.out.println(arr[i]);
        }
    }

    public static void func(int n, int x, int y){
    	// 더 이상 할 수 없을 때까지 반복
        if(n==1){
            return;
        }
        int size = n/3;
        
        // 가운데 빈칸 처리하기
        for (int i = x + size; i < x + (size*2) ; i++) {
            for (int j = y + size; j < y + (size*2) ; j++) {
                arr[i][j] = ' ';
            }
        }
        
        // 작은 9개의 네모 재귀적으로 호출
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
            	// 이미 처리한 가운데는 넘어가기
                if(i == 1 && j == 1) continue;
                // 작은 크기의 네모 호출
                func(size, x+i*size, y+ j*size);
            }
        }
    }
}