[240227] 알고리즘 리부트 18일차 - 백준 2447 자바

 

개인적으로 재귀를 직관적으로 이해하는 게 많이 어려웠다. 그래서 재귀를 다시 익숙하게 만들기 위해서 그나마 정답률이 높은 이 문제를 선택했지만 고민을 해봐도 영 감이 잡히지 않아서 풀이를 참고해서 풀었다. 그나마 할 수 있는 건 풀이를 보고 따라치는 게 아니라 손으로 스택에 함수를 쌓아가며 다시 의사코드를 작성해보고 이를 다시 코드로 옮기면서 로직을 이해하려 노력했다. 

여기서도 문제를 작게 나눠서 보는 것이 필요한데 n이 3일 때는 3*3의 배열을 가진 칸에 5번째 칸 즉, (1,1) 칸이 비어있어야 한다. n이 9인 경우에도 9*9의 배열이지만 각각의 3*3의 배열로 이루어져 있어서 5번째 3*3 즉, (3,3) 부터 우하향으로 (5,5)까지의 배열이 비어있어야 한다. 이걸 깨달은 사람은 천재들인가..라는 생각을 했지만 나도 천재될 수 있다는 생각으로! 

3*3부터 접근해서 별 하나씩 그려야하기 때문에 주어진 n에서 부터 3씩 나누어가면 재귀 호출을 진행한다. n이 1일 때 비로소 그리기 시작하는데 count 가 5일 때, 즉, 5번째에 위치한 경우에는 해당하는 영역을 비워두어야 한다. 이를 위해 논리값 변수를 하나 두고, count 변수를 이용해 해당 재귀 함수 내에서 그리게 될 때마다 count를 올려줘야 한다. 코드를 까먹을 때 쯤에 다시 풀어야겠다.

 

import java.util.Scanner;

public class Main {
    public static char[][] sky;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        sky = new char[n][n];

        drawStars(0, 0, n, false);

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sb.append(sky[i][j]);
            }
            sb.append("\n");
        }

        System.out.println(sb);

    }

    private static void drawStars(int x, int y, int n, boolean blank) {

        if (blank) {
            for (int i = x; i < x + n; i++) {
                for (int j = y; j < y + n; j++) {
                    sky[i][j] = ' ';
                }
            }
            return;
        }

        if (n == 1) {
            sky[x][y] = '*';
            return;
        }

        int newN = n / 3;
        int count = 0;

        for (int i = x; i < x + n; i += newN) {
            for (int j = y; j < y + n; j += newN) {
                count++;
                if (count == 5) {
                    drawStars(i, j, newN, true);
                } else {
                    drawStars(i, j, newN, false);

                }
            }
        }
    }
}