백준 2447번 별찍기 10 - 자바(Java)

문제 링크

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

 

---

1. 문제

문제

재귀적인 패턴으로 별을 찍어 보자. 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번째 줄까지 별을 출력한다.

2. 문제 관찰 과정 및 풀이

2-1. 문제 관찰 과정

가장 먼저 구멍이 먼저 눈에 들어왔다

별 찍기 문제이지만 별을 직접 찍는다면 제일 큰 네모의 별을 찍고

들어가서 또 별과 빈칸을 찍어야한다는 것인데 너무 중복이 많을 것 같아 제일 처음에

*로 세팅해두고 빈칸을 비워내는 방식으로 진행해야겠다고 생각했다.

2-2. 문제 풀이

1. n x n 의  char배열을 만들어준다.
2. Arrays.fill로 모두 *로 채워준다.
3. 재귀함수인 recur을 실행한다.
   1. size값을 받은뒤 나누기 3을 하여 저장한다.
   2. 나누기 3한 값을 매개 변수였던 좌표에 더해 비워주어야 할 부분을 ' ' 로 바꾸어준다.
   3. 비운 중간을 제외한 위에 3부분, 중간에 양쪽, 제일 밑에 3부분을 재귀로 반복한다.
   4. 만약 size가 3이 된다면 중간에 만 ' ' 를 넣어주고 return한다.

3. 코드

import java.io.*;
import java.lang.reflect.Array;
import java.util.Arrays;

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

        int n = Integer.parseInt(br.readLine());
        map = new char[n][n];

        for(int i = 0;i<n;i++){
            Arrays.fill(map[i], '*');
        }

        recur(n, 0 , 0);

        StringBuilder sb = new StringBuilder();

        for(int i = 0 ; i< n; i++){
            for(int j = 0;j<n;j++){
                sb.append(map[i][j]);
            }
            sb.append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
    public static void recur(int size, int x , int y){
        if(size == 3){
            map[x + 1][y+ 1] = ' ';
            return;
        }

        int nextSize = size / 3;
        for(int i = x + nextSize; i < x + nextSize * 2; i++){
            for(int j = y + nextSize; j < y + nextSize * 2;j++){
                map[i][j]  = ' ';
            }
        }


        recur(nextSize, x, y);
        recur(nextSize, x + nextSize, y);
        recur(nextSize, x + nextSize * 2, y);

        recur(nextSize, x, y + nextSize);
        recur(nextSize, x+ nextSize * 2, y + nextSize );

        recur(nextSize, x , y + nextSize * 2);
        recur(nextSize, x + nextSize, y + nextSize * 2);
        recur(nextSize, x + nextSize * 2, y + nextSize * 2);


    }
}

3-1. 실행 결과

4. 여담

인터넷에 다른 사람들 풀이를 잠깐 찾아봤는데 아무도 이렇게 푼 사람이 없다....

독창적인 방법이라 마음에 들었다!

다만 fill을 하는게 느릴까봐 고민되었다.