[BaekJoon] 2447 별 찍기 - 10 (Java)

1.  문제 링크

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

2.  문제

요약

• N이 3의 거듭제곱이라고 할 때, 크기 N의 패턴은 NxN 정사각형 모양입니다.
• 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴입니다.
• N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데 (N / 3) * (N / 3) 정사각형을 크기 N / 3의 패턴으로 둘러싼 형태입니다.
• N이 주어졌을 때, 패턴에 맞는 별을 출력하는 문제입니다.
• 입력: 첫 번째 줄에 N이 주어집니다. $N=3^k$이며 k는 1보다 크거나 같고 8보다 작거나 같습니다.
• 출력: 첫 번째 줄부터 N개의 줄에 별을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static char[][] stars;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		stars = new char[N][N];
	}
	
	static void rec_func(int x, int y, int cur_size, boolean blank) {
		if(blank) {
			for(int i = x; i < x + cur_size; i++) {
				for(int j = y; j < y + cur_size; j++) {
					stars[i][j] = ' ';
				}
			}
			return;
		}
		if(cur_size == 1) {
			stars[x][y] = '*';
			return;
		}
		int size = cur_size / 3;
		int count = 0;
		for(int i = x; i < x + cur_size; i += size) {
			for(int j = y; j < y + cur_size; j += size) {
				count++;
				if(count == 5) {
					rec_func(i, j, size, true);
				} else {
					rec_func(i, j, size, false);
				}
			}
		}
	}
	
	static void print() {
		for(int i = 0; i < stars.length; i++) {
			for(int j = 0; j < stars[i].length; j++) {
				sb.append(stars[i][j]);
			}
			sb.append('\n');
		}
		System.out.println(sb.toString());
	}
	
	public static void main(String[] args) {
		input();
		rec_func(0, 0, N, false);
		print();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

4.  접근

• N x N 크기의 정사각형 모양은 (N / 3) x (N / 3) 크기의 정사각형 9개로 채웁니다.
• N x N 크기의 정사각형 모양에서 가운데에는 공백으로 채워지는데 이는 (N / 3) x (N / 3)을 오른쪽 방향으로 하나씩 채워나간 후에 한 줄을 모두 채우면 아래 줄로 내려와 같은 방식으로 채워나가는 방식으로 N x N 크기의 정사각형을 채운다면 5번째 위치가 공백이 된다는 것을 확인할 수 있습니다.
• 즉, 각 정사각형을 채울 때 (N / 3) x (N / 3) 크기의 5번째 위치가 공백으로 채워진다는 것을 이용하여 공백을 처리합니다.
  
  
• N x N 배열 stars를 생성하는데 각 위치에는 별 또는 공백이 들어갑니다.
• 각 위치에 들어가는 문자는 재귀를 통해 결정합니다.
• rec_func() 함수를 생성하는데, 이는 4개의 파라미터를 갖습니다.
  • 현재 위치의 x좌표와 y좌표를 나타내는 x, y, 현재의 크기를 나타내는 cur_size, 빈칸에 해당하는지를 나타내는 blank를 파라미터로 갖습니다.
• 현재 크기의 정사각형을 채울 때 (현재 크기 / 3) 크기의 정사각형으로 채우기 때문에 size 변수에 (현재 크기 / 3) 값을 저장합니다.
• 현재 크기의 정사각형을 채울 때 현재 채우는 위치가 몇 번째인지 나타내기 위해 count 변수를 생성하고 값을 0으로 초기화합니다.
• (x, y)부터 현재 크기의 정사각형 각 위치를 돌며 공백인 곳을 찾습니다. 이 때, (현재 크기 / 3) 크기의 정사각형으로 채우기 때문에 반복문 한 번마다 size만큼 이동합니다.
  • count를 1 증가시키고 count가 5인지 아닌지 판단합니다.
  • 만약 count가 5라면 해당 칸은 공백이 되어야 하는 칸이기 때문에 현재 위치의 좌표 (x, y), size, true를 각각 파라미터로 하여 재귀함수 호출을 진행합니다.
  • 만약 count가 5가 아니라면 해당 칸은 별로 채워져야 하는 칸이므로 현재 위치의 좌표 (x, y), size, false를 각각 파라미터로 하여 재귀함수 호출을 진행합니다.
• 만약 blank가 true라면 현재 위치가 빈칸 위치임을 나타내기 때문에 (x, y)부터 현재 크기만큼을 공백으로 채우고 재귀함수 호출을 중단합니다.
• 만약 cur_size가 1이라면 이전에 blank가 false인지 확인하였기 때문에 별로 채워야 하는 위치인 것은 확인이 되었는데 cur_size가 1이라는 뜻은 더이상 해당 정사각형을 더 작은 크기의 정사각형들로 채울 수 없다는 뜻이므로 해당 위치를 별로 채워줍니다.