백준 2447 - 별 찍기 - 10

문제링크

• 백준 2447

문제 설명

***
* *
***      <- 별을 찍는 패턴. 3x3 크기의 패턴
N은 3의 거듭제곱(3,9,27,...) 로 주어지고, 
1. N>3 인 경우, 가운데 (N/3)x(N/3) 부분은 공백
2-1. 나머지 부분에 대해서 마찬가지로 N>3 인 경우, 1 반복
2-2. N=3 인 경우, 별 패턴 찍어내기

문제 접근 방향(bokyoung)

• 출력을 하면서 문제를 풀기에는 구현이 너무 복잡하다.
• NxN char형 2차원 배열을 만들고 *과 공백을 좌표로 구분하자.
  • 인덱스는 1~N으로 결정
• 3x3 기본 패턴을 배열에 채워주는 재귀함수를 만든다. make_pattern(int start_x, int strat_y, int step)
• 패턴은 정사각형 좌측 상단 -> 우측 하단 으로 이동하며 채워지고, 5번째 칸은 공백으로 둔다.
• 재귀의 기저사례는 step==1이 되었을 때로, 이때 pattern을 채운다.

구현 결과

#include <iostream>
#include <vector>
using namespace std;

// pattern을 정사각형 배열에 입력하는 재귀함수
// 좌측상단에 위치하는 시작좌표와 다음 좌표로 이동하는 간격 step을 인자로 받는다.
// step==1인 경우 3x3 기본 패턴을 입력한다.
// 정사각형에서 중앙에 위치(5번째 탐색 칸)하는 칸은 공백으로 두어야 한다.
void make_pattern(vector<vector<char>>& square, int start_x, int start_y, int step)
{
	// 기저사례
	if (step == 1)
	{
		int flag = 0; // 5번째 입력하는 경우는 공백으로 둔다.
		for (int r = start_x, cnt_x=0; cnt_x<3; r++, cnt_x++)
		{
			for (int c = start_y, cnt_y=0; cnt_y < 3; c++, cnt_y++)
			{
				flag += 1;
				if (flag == 5) continue;
				square[r][c] = '*';
			}
		}
		return;
	}
	
	int flag = 0;
	for (int r = start_x, cnt_x = 0; cnt_x < 3; r += step, cnt_x++)
	{
		for (int c = start_y, cnt_y = 0; cnt_y < 3; c += step, cnt_y++)
		{
			flag += 1;
			if (flag == 5) continue;
			make_pattern(square, r, c, step / 3);
		}
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	cin >> N;
	vector<vector<char>> square(N+1, vector<char>(N+1, ' ')); // 공백 문자로 채워진 2차원 배열을 형성
	make_pattern(square, 1, 1, N / 3);
	
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
			cout << square[r][c];
		cout << endl;
	}
	return 0;
}