[백준] 2447 - 별 찍기 10 (자바/Java): 재귀

문제

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

---

설명 참고: https://velog.io/@sossont/%EB%B0%B1%EC%A4%80-2447%EB%B2%88-%EB%B3%84-%EC%B0%8D%EA%B8%B0-10

 

처음에는 2차원 배열을 사용하지 않고 string에 계속 더하는 식으로 풀었는데, 시간이 오래 걸리고 재귀를 잘 활용한 것 같지도 않았다.

그래서 2차원 배열에 담는 식으로 구현하였다. 처음에는 모두 공백으로 채우고, N부터 시작해서 N/3 ... N이 1이 될 때까지 반복한다.

각 블럭에서 i=1, j=1인 경우, 즉 가운데의 경우는 공백이기 때문에 함수를 호출하지 않고 공백인 상태로 둔다.

9개의 블럭을 기준으로 가운데 블럭에만 공백을 출력하면 된다.

N=3^k에서 k는 1씩 감소하고, 그때마다 가운데 블럭만 비운채로 별을 출력하면 되기 때문에 이를 생각하며 알고리즘을 짠다.

N이 9일 때 기준으로 *이 출력되는 index는 다음과 같다.

i  j
0 1 
0 2 
1 0 
1 2 
2 0 
2 1 
2 2 // 블럭1

0 3 
0 4 
0 5 
1 3 
1 5 
2 3 
2 4 
2 5 // 블럭2

...

3 0 
3 1 
3 2 
4 0

4 2 
5 0 
5 1 
5 2 // 블럭4

 

(3 3) ~(5 5) : 가운데 블럭이므로 공백

... 반복

 

코드

package BOJ0729;

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;

public class BOJ_2447_별찍기10_arr {
	static char[][] arr;
	static int N;

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = sc.nextInt();
		arr = new char[N][N];
		for (int i = 0; i < N; i++)
			Arrays.fill(arr[i], ' ');

		stars(0, 0, N);
		for (int i = 0; i < N; i++) {
			bw.write(arr[i]);
			bw.newLine();
		}
		bw.flush();
	}

	static void stars(int x, int y, int N) {
		if (N == 1) {
			arr[x][y] = '*';
			return;
		}

		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (i == 1 && j == 1)
					continue; // i와 j가 1일 때는 공백
				stars(x + (N / 3) * i, y + (N / 3) * j, N / 3);
				// N/3을 기준으로 가운데(i=1, j=1)일 때는 공백임 -> 이걸 재귀로 반복
			}
		}

	}

}