[백준 알고리즘][자바] 2447번 : 별 찍기 - 10

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

2447번: 별 찍기 - 10

재귀 함수를 이용한 별 찍기 문제입니다.

첫째 줄에 주어지는 숫자 N은 3의 거듭제곱입니다.(3, 9, 27, 81...)

크기가 3인 패턴은 위와 같이 가운데가 비어진

***
* *
***

패턴입니다.

만약 N이 3보다 큰 수(9, 27, 81..) 일 때는 크기 N/3의 패턴으로 둘러싼 형태입니다.

즉 문제에서 주어진 27의 패턴은 아래와 같습니다.

처음 문제를 접근한 방법은 재귀함수를 이용해 별을 String으로 만들어주는 방식으로 코드를 짰습니다.

package number_2447;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

// 		백준 알고리즘 2447번
//		재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.
//		크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.
//		***
//		* *
//		***
//		N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		
		String star = "***\n* *\n***";

		String N_pattern = N_pattern(star, N);
		
		bw.write(N_pattern);
		
		br.close();
		bw.flush();
		bw.close();
		
		
	}
	
	public static String N_pattern(String star, int N) {
		
		if(N / 3 == 1) {
			return star;
		}else {
			N = N / 3;
			return N_pattern(star, N)+N_pattern(star, N)+N_pattern(star, N)+"\n"+N_pattern(star, N)+" "+N_pattern(star, N)+"\n"+N_pattern(star, N)+N_pattern(star, N)+N_pattern(star, N);
		}
	}
}

 위와같이 만드니 줄 바뀜이 다른 문자열에 영향을 주어서 아래와 같이 나오더군요

이 결과를 보고 알 수있는 점은 개행 문자는 안의 요소에서 바꾸어주지 않고 N이 최대 크기일 때 개행해줘야 한다.

즉, 별을 묶음으로 찍어주는게 아닌 하나하나 찍어줘야 한다.

그래서 저는 배열을 사용하기로 했습니다.  

 

배열로 *을 채워나간다고 했을 때 고려해야 할 점들은 아래와 같습니다.

1. N이 주어졌을 때 배열은 N X N 패턴이다.
2. 배열의 중간 즉, (1,1)은 비어져야 한다.
3. 패턴이 반복되는 지점은 N/3 지점이다.

즉, 별을 채우지 않는 중간 부분을 배열의 위치, 반복문의 변수, N/3으로 특정해줘야 합니다.

 

크기가 27일때 크기가 9인 패턴으로 분할하여 시작 좌표로 나타내면 다음과 같습니다.(Y = 0 일 때만)

1. X = 0, Y = 0, N = 9 => (0, 0, 9)
2. X = 9, Y = 0, N = 9 => (9, 0, 9)
3. X = 18, Y =0, N = 9 => (18, 0, 9)

다시 크기가 9일 때 크기가 3인 패턴으로 분할하여 시작 좌표로 나타내면 다음과 같습니다.

1. X = 0, Y = 0, N = 3 => (0, 0, 3)
2. X = 3, Y = 0, N = 3 => (3, 0, 3)
3. X = 6, Y = 0, N = 3 => (6, 0, 3)

즉 X의 좌표는 0*N, 1*N, 2*N... 이렇게 정해집니다. 정사각 형태의 배열이기 때문에 Y좌표도 동일합니다.

만약 다른 위치의 좌표라면 X의 좌표 + 0*N, X의 좌표 + 1*N, X의 좌표 + 2*N... 이렇게 정해집니다.

 

이것을 함수의 수식으로 나타내면 아래와 같습니다.

// 분할하였을 때의 좌표
for(int i = 0 ; i < 3 ; i++){
	for(int j = 0 ; j < 3 j++){
    	star(starArr, x + i*(N/3), y + j*(N/3), N/3);
    }
}

이런 식으로 재귀 호출을 하여 분할을 완료했을 때, 중간 부분은 별을 채우면 안 되기 때문에 호출을 하지 않고

크기 N이 1이 되었을 때 별을 채워주도록 합니다.

package number_2447;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

// 		백준 알고리즘 2447번
//		재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.
//		크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.
//		***
//		* *
//		***
//		N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		String[][] starArr = new String[N][N];

		for(int i = 0 ; i < N ; i++) {
			for(int j = 0 ; j < N ; j++) {
				starArr[i][j] = " ";
			}
		}
		
		star_pattern(starArr, 0, 0, N);
		
		for(int i = 0 ; i < N ; i++) {
			for(int j = 0 ; j < N ; j++) {
				bw.write(starArr[i][j]);					
			}
			bw.write("\n");
		}
		
		br.close();
		bw.flush();
		bw.close();
		
		
	}
	
	public static void star_pattern(String[][] starArr, int x, int y, int N) {
		
		if(N == 1) {
			starArr[x][y] = "*";
			return;
		}
		
		for(int i = 0 ; i < 3 ; i++) {
			for(int j = 0 ; j < 3 ; j++) {
				if(!(i == 1 && j == 1)) {
					star_pattern(starArr, x + i*(N/3), y + j*(N/3), N/3);
				}
			}
		}
	}
}