백준 2447번 : 별 찍기 -10 java

 

이 문제에는 왼쪽 그림과 같이 큰 정사각형의 그림을 9 등분해서 각각의  영역으로 나누어 나타낼 수 있습니다.

 

 

1 2 3          이런 식으로 각 공간에 숫자를 붙인다면 1 2 3 4 6 7 8 9가 
4 5 6          채워져 있고 5만 패턴이 없는 비어있는 형태입니다.
7 8 9

 

 

우리는 이러한 반복되는 성질을 이용하여 이 문제를 해결할 수 있습니다.

 

이렇게 반복되는 패턴이 주어지는 수에 따라서 달라지는 경우 우리는    재귀를 이용해서 문제를 해결할 수 있습니다.

 

이제 재귀를 이용해 문제를 풀어보도록 하겠습니다.

 

---

 

import java.io.*;

public class Main{
    static char[][] array;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        array = new char[N][N];

        recursion(0, 0, N, true);

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

        System.out.print(sb);
    }

    public static void recursion(int row, int col, int N, boolean isStar){
        int count = 0;

        if(N == 1){
            if(isStar)
                array[row][col] = '*';
            else
                array[row][col] = ' ';
            return;
        }

        for(int i = row; i<row+N; i += N/3){
            for(int j = col; j<col+N; j += N/3){
                if(++count != 5 && isStar)
                    recursion(i, j,N/3,true);
                else
                    recursion(i, j, N/3, false);
            }
        }
    }
}

저는 이 문제를 풀기 위해서 2차원의 배열을 선언하였습니다. 각 변의 길이가 3분의 1로 줄어들 때 줄어든 곳에서의    패턴을 저장하기 위해서는 배열을 이용하여 저장한 후 나중에 한 번에 출력하는 것이 편리하다 판단했기 때문입니다.

그리고 각 시작점에서 그 다음 재귀에서 한 변의 길이인 N/3을 추가한 곳까지를 한 구역으로 놓고 위에서 설명한 대로 구역을 나누어 count가 5가 되는 곳은 전부 비우기 위해서 isStar 변수를 사용하였습니다.

5번째가 되는 구역 안에서는 그 안에서 재귀가 일어나더라도 항상 비어있어야 되므로 isStar 변수를 false로 만들어주어 별이 출력되지 않도록 구현하였습니다.