개발하는 호랑이

반가워욤 :)

4 분 소요

문제

백준 2447번 별찍기 10 문제

문제 풀이

어떻게 풀어야할지 막막했던 문제이다.
그림을 보고 대략적인 규칙은 알았지만 그걸 구현하는 방법이 감이 잡히질 않았다.

규칙

문제를 보자.

  1. N이 3의 거듭제곱(3, 9, 27 …)이라고 할 때, 크기 N의 패턴은 \(N * N\)의 정사각형 모형이다.
    크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

    결국 N이 3일 때는 이러한 모양이 될 것이다.

  2. N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다.
    N이 3보다 큰 경우는 \(3^2, 3^3, 3^4 …\)이다.

    N = \(3^2\) = 9일 경우 위와 같이 3x3 패턴이 둘러 싸고 있고 가운데에는 (9/3)x(9/3) = 3x3의 공백이 있는 모양이고

    N = \(3^3\) = 27일 경우 위와 같이 9x9 패턴이 둘러 싸고 있고 가운데에는 (27/3)x(27/3) = 9x9의 공백이 있는 모양이다.
    보자마자 알겠지만 결국 3x3의 패턴이 연속적으로 채워져 만들어진다는 것을 알 수 있다.

1.


N이 9라고 가정하면 사진에서 빨간색으로 표시한 곳을 기준으로 3x3 패턴이 시작되는 것을 알 수 있다.

char[][] arr = new char[9][9];

위와 같은 배열을 만든다면 3x3 패턴의 시작점은 아래와 같을 것이다.

이걸 반복문으로 각 시작점을 찾을려면 아래와 같이 하면된다.

char[][] arr = new char[9][9];

// 빨간점의 위치가 N이 9일 때는 3씩 증가한다.
for(i = 0; i < 9; i += 3){	
	for(j = 0; j < 9; j += 3){
		arr[i][j] = '*';
	}
}

그리고 여기에 가운데는 공백이어야 한다는 조건을 추가시켜보자.
가운데는 arr[3][3]으로 [0][0], [0][3], [0][6], [3][0], [3][3] 순서이므로 5번째가 공백이 된다.
5번째인 것을 체크하기위해 count를 넣어 공백까지 처리해보자.

char[][] arr = new char[9][9];

int count = 0;
// 빨간점의 위치가 N이 9일 때는 3씩 증가한다.
for(i = 0; i < 9; i += 3){	
	for(j = 0; j < 9; j += 3){
		count++;
		if(count == 5){
			arr[i][j] = ' ';
		} else {
			arr[i][j] = '*';
		}
	}
}

이제 문제는 각 시작점에 * 하나가 아니라 3x3의 패턴을 찍어줘야 한다는 것이다.
그러기 위해서 저 부분을 재귀함수로 만들어보자.

char[][] arr = new char[9][9];

star(0, 0, 9, arr);

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

	int count = 0;

	for(i = x; i < x + N; i += N/3){	
		for(j = y; j < y + N; j += N/3){
			count++;
			if(count == 5){
				arr[i][j] = ' ';
			} else {
				star(i, j, N/3, arr);
			}
		}
	}
}

재귀함수로 만들어주기 위해 위처럼 반복문의 조건을 바꿔주고 N이 1일 때 *를 배열에 넣어주도록 하였다.
천천히 하나씩 보면

  • 처음 실행되면 N = 9, x = 0, y = 0 이고, x와 y는 3씩 증가할 것이다.
  • 반복문안의 star에 매개변수로 N = 3, x = 0, y = 0 을 넘겨주며 실행되고
  • 그 다음 또 반복문을 타서 star에 매개변수로 N = 1, x = 0, y = 0을 넘겨주며 실행된다.
  • 그러면 이제 N이 1이므로 맨위의 if문의 조건에 맞기 때문에 arr[0][0]에 *를 넣어주고 함수가 리턴되 종료되고
  • 앞선 반복문에서 N은 1씩 증가하므로 반복문을 돌며 3x3패턴을 그려나갈 것이다.
  • 위와 같은 과정을 반복해 순차적으로 각 시작점에서 3x3 패턴을 그릴 것이다.

하지만 이렇게 한다면 9x9 패턴의 가운데에 3x3 공백 패턴을 그려내지 못할 것이다.
이 부분을 해결하기위해 재귀함수에 하나의 조건을 더 추가해주자.

char[][] arr = new char[9][9];

star(0, 0, 9, arr, false);

void star(int x, int y, int N, char[][] arr, boolean flg){
	if(flg){
		for(int i = x; i < x + N; i++){
			for(int j = y; i < y + N; j++){
				arr[i][j] = ' ';
			}
		}
		return;
	}

	if(N == 1){
		arr[x][y] = '*'
		return;
	}

	int count = 0;

	for(i = x; i < x + N; i += N/3){	
		for(j = y; j < y + N; j += N/3){
			count++;
			if(count == 5){
				star(i, j, N/3, arr, true);
			} else {
				star(i, j, N/3, arr, false);
			}
		}
	}
}

공백을 표시하기 위해 위처럼 if문을 넣어줬다.
N이 9일 경우 arr[3][3]부터 arr[5][5]까지 공백을 넣어줘야하므로 count가 5일 때 x = 3, y = 3, N = 3을 star에 매개변수로 넘겨준다. 그러면 반복문을 통해 arr[3][3]에 3x3의 공백패턴을 넣을 수 있다.

설명을 위해 N이 9일때를 가정하여 천천히 풀어나갔지만 위처럼 재귀함수를 만들면 N과 상관없이 모두 표현이 된다.

2.

결과적으로 아래처럼 작성하면 된다.

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		char[][] arr = new char[N][N];

		star(0,0,N,arr,false);

		StringBuilder sb = new StringBuilder();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				sb.append(arr[i][j]);
			}
			sb.append('\n');
		}
		System.out.print(sb);
	}


	public static void star(int x, int y, int N, char[][] arr, boolean flg){
		if(flg){
			for(int i = x; i < x + N; i++){
				for(int j = y; i < y + N; j++){
					arr[i][j] = ' ';
				}
			}
			return;
		}
		
		if (flg) {
			for (int i = x; i < x + N; i++) {
				for (int j = y; j < y + N; j++) {
					arr[i][j] = ' ';
				}
			}
			return;
		}

		if(N == 1){
			arr[x][y] = '*';
			return;
		}

		int count = 0;

		for(int i = x; i < x + N; i += N/3){	
			for(int j = y; j < y + N; j += N/3){
				count++;
				if(count == 5){
					star(i, j, N/3, arr, true);
				} else {
					star(i, j, N/3, arr, false);
				}
			}
		}
	}
}

참고하며 공부한 블로그

참고