[BOJ] 2447 - 별 찍기 - 10 JAVA

www.acmicpc.net/problem/2447

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이다.

출력

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

예제 입력 1

27

예제 출력 1

제대로 찍을 수가 없다.

BOJ에서 직접 확인.

 

 

 

 

 

 

 

풀이 .

import java.io.*;

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringBuilder sb = null;
    static char[][] arr = null;

    public static void putSpace(int row, int col, int len) {
        for(int i = row; i < row + len; i++ ) {
            for(int j = col; j < col + len; j++) {
                arr[i][j] = ' ';
            }
        }
    }

    public static void divideAndConquer(int row, int col, int len) {  // row, col은 시작행, 시작열
        if(len == 1) {
            arr[row][col] = '*';
            return;
        }

        int nextLen = len / 3;
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                if(i == 1 && j == 1) {  // 큰 덩어리의 [2][2]은 공백 출력
                    putSpace(row + i*nextLen, col + j*nextLen, nextLen);
                }else {
                    divideAndConquer(row + i*nextLen, col + j*nextLen, nextLen);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        arr = new char[n+1][n+1];
        divideAndConquer(1, 1, n);

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

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

 

예전에 이 문제를 처음 봤을 때 어마어마한 출력문을 보고 쫄아서 바로 닫아버렸던 기억이 있다.

 

재귀를 어떻게 풀어나가야 할 지 떠올리는 것은 어렵지 않았지만 구현은 좀 까다로웠던 것 같다.

엄청나게 어려운 문제는 아니지만 다른 문제보다도 이 문제를 풀고 나니 뭔가 실력이 조금은 향상됐다는 느낌이 들기도 한다.

 

 

처음에 가장 고민했던 부분은 출력의 줄바꿈을 어떻게 해줘야 할 지 였다.

재귀 조건은 간단했지만 재귀 내부에서 공백을 넣으려고 하니 정상적인 출력을 뽑아낼 수 없기 때문이다.

 

알고보니 이차원 배열로 간단하게 해결할 수 있었다. N x N 사이즈 이차원 배열의 각 좌표에 '*' or ' ' 을 넣고, 모든 재귀가 끝난 후에 배열 원소들을 출력해주면 된다.

 

고정관념에 사로잡혀서 모든 처리를 재귀 안에서 해주려고 하다보니 배열을 사용한 간단한 해결책을 생각하지 못했다.

 

큰 덩어리를 9개로 나눈다는 것이 codeung.tistory.com/194 와 비슷하다.

N x N 크기의 덩어리를 아홉개로 나눴을때 한 덩어리에 N/3 크기인 덩어리들이 [3][3]으로 있다고 생각할 수 있다.

 

문제의 조건에 따라 가운데 덩어리인 [2][2]은 공백으로 채워줘야 한다.

(0행 0열은 사용하지 않는다 하고)

 

Length가 1이 될 때까지 재귀를 반복하고 1일 되면 별을 넣어준 후 return하면 된다.