[BOJ 2447번] 별 찍기 - 10

[BOJ] 2447번 별 찍기 - 10

 

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

2447번: 별 찍기 - 10

 

이 문제는 전형적인 분할 정복, 재귀의 문제이다. 이 문제의 설명에서도 언급했듯이 재귀적인 패턴으로 별을 찍는 문제이다.

 

문제의 설명은 다음과 같다

 

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27,...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. 문제에서 핵심이 되는 포인트는  "크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다" 라고 설명한 부분이라고 볼 수 있다. 설명은 그만하고 그림으로 살펴보자 어떻게 재귀적인 패턴을 띈다고 볼 수 있을까?

 

1. 재귀적인 패턴 살펴보기

 

 

먼저 재귀적인 패턴을 보도록 하자. 위의 사진을 보자 3 x 3의 정사각형에서 가운데가 뻥 뚫려 있는 것을 알 수 있다. 이 정사각형이 다시 3 x 3으로 모이면 어떤 형태일까? 

 

 

초기의 패턴을 3 x 3으로 모았더니 가운데만 뻥 뚫려 있다. 즉 가운데만 패턴이 없다. 그렇다면 다시 주황색 정사각형의 패턴이 3 x 3 으로 모아 보면 밑의 사진과 같다. 

 

 

이 사각형도 보면 가운데가 뻥 뚫려 있음을 알 수 있다. 어떤가.. 재귀적인 패턴이 보이는가.....???? 그렇다면 도대체 문제는 어떻게 풀것인가??  27 x 27 별을 출력을 해야 한다.  앞에서 살펴봤던 것처럼 작은 사각형에서부터 출력한다는 것은 말이 안 된다.  문제 풀이에 있어서는 반대로 접근 할 것이다. 우리는 27 x 27 배열 (보드) 에 별을 찍는 것이 목표이다. 다시 한번 말하지만 배열에 별을 채울 것이다.

 

 

2. 구현 아이디어

 

 

그에 앞서 우리는 하나의 정사각형이 그 보다 작은 정사각형이 3 x 3으로 모여서 만들어진다는 것을 알았다. 27 x 27 배열에 별을 찍는 것이 목표이다. 별을 배열에 넣기에는 아직 크다. 그렇다면 더 쪼개 보자!!  여기서 주의해야 할 점은 9개의 정사각형이 존재하는데 9개의 정사각형 하나하나 모두 쪼개야 한다는 사실이다. 그렇다면 반복문으로 순회하면서 위의 사진과 같은 순서로 모두 쪼갤 수 있지 않을까?? 

 

 

그래 1번 사각형을 다시 쪼개 보자!

 

 

이 정도 쪼갰으면 되지 않았는가?? 또한 가운데가 뚫려 있다는 사실에 주목해서 구현해보자. 사실 이런 아이디어를 얻고 나머지는 본인의 구현력으로 구현해보는 것이 가장 좋은 훈련이라고 생각이 된다. 그렇기 때문에 자세하게 코드를 하나하나 설명 것은 제외하고자 한다. 

 

 

3. 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Scanner;
 
public class Main {
    static boolean[][] board = new boolean[6561][6561];
 
    public static void main(String[] args) throws NumberFormatException, IOException {
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
         int N = Integer.parseInt(br.readLine());
        solve(N, 0, 0, false);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(!board[i][j])  bw.write("*"); 
                else  bw.write(" ");
            }
            bw.write("\n");
        }
         bw.flush();
         bw.close();
         br.close();
    }
    public static void solve(int N, int x, int y, boolean blank) {
        if (N == 1) {
            if (blank)
                board[x][y] = true;
        } else {
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {    
                    int step = N / 3;
                    boolean nextBlank = ((!blank && i == 1 && j == 1) ? true : false);
                    solve(N / 3, x + i * step, y + j * step, blank || nextBlank);
                }
            }
        }
    }