๋ฌธ์ œ

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

ํ’€์ด

์ด ๋ฌธ์ œ์—์„œ ๋‚˜์˜ค๋Š” ์˜ˆ์‹œ์ถœ๋ ฅ์„ ๋ณด๋‹ˆ ๊ณ ๋“ฑํ•™๊ต ๋ฏธ์ ๋ถ„ ๊ณผ์ •์˜ ๋ฌดํ•œ๋“ฑ๋น„๊ธ‰์ˆ˜ ๋‹จ์›์— ์ถœํ˜„ํ•˜๋Š” ๋ฌธ์ œ์ค‘ ๋ฌดํ•œ ๋“ฑ๋น„ ๊ธ‰์ˆ˜๋ฅผ ํ™œ์šฉํ•œ ๋„ํ˜•์˜ ๋„“์ด๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ๊ฐ€ ๋จผ์ € ๋– ์˜ฌ๋ž๋‹ค.

(๋Œ€์ถฉ ์š”๋Ÿฐ๊ฑฐโ€ฆ) ์ถœ์ฒ˜ : https://m.blog.naver.com/jamogenius/220886627296

์ข€๋” ์กฐ์‚ฌํ•ด๋ณด๋‹ˆ ์ด๋Ÿฐ ๋„ํ˜•์„ ํ”„๋ž™ํƒˆ ๋„ํ˜•(fractal pattern) ์ด๋ผ๊ณ  ํ•œ๋‹ค๊ณ  ํ•œ๋‹ค.

๋ฐฐ๊ฒฝ ์ง€์‹์€ ์š”์ •๋„๋ฉด ๋œ๊ฒƒ ๊ฐ™๊ณ  ์ด ๋ฌธ์ œ๋ฅผ ์‚ดํŽด๋ณด๋ฉด ์•„๋ž˜์™€ ๊ฐ™์€ ๋ฌธ์–‘์ด ์ ์  ์ž‘์•„์ง€๋ฉด์„œ ๊ฐฏ์ˆ˜๊ฐ€ ๋งŽ์•„์ง€๋ฉฐ ๋ฐ˜๋ณต๋˜๋ฉฐ ํ”„๋ž™ํƒˆ ๋„ํ˜•์˜ ํ˜•ํƒœ๋ฅผ ๋„๋Š” ๊ฒƒ์„ ํ™•์ธํ•  ์ˆ˜ ์žˆ๋‹ค.

***
* *
***

๊ทธ๋ž˜์„œ ๋‚˜๋Š” ํ”„๋ž™ํƒˆ ๋„ํ˜•์ด ๊ทธ๋ ค์ง€๋Š” ๊ณผ์ •์„ ๊ทธ๋Œ€๋กœ ์†Œ์Šค์ฝ”๋“œ์— ์ ์šฉํ•ด๋ณด๊ธฐ๋กœ ํ–ˆ๋‹ค.

๋ฐ”๋กœ ํฐ ๋„ํ˜•์„ ๋จผ์ € ๊ทธ๋ฆฌ๊ณ  ๊ทธ ์ดํ›„ ์ž‘์€ ๋„ํ˜•์„ ๊ทธ์œ„์— ๋ฎ์–ด ์”Œ์šฐ๊ณ  ๊ทธ ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•˜๋„๋ก ํ•˜๋Š” ๊ฒƒ์ด๋‹ค.

์˜ˆ๋ฅผ๋“ค์–ด ์ž…๋ ฅ ๊ฐ’์ด 27์ผ๋•Œ

***************************
***************************
***************************
***************************
***************************
***************************
***************************
***************************
***************************
*********         *********
*********         *********
*********         *********
*********         *********
*********         *********
*********         *********
*********         *********
*********         *********
*********         *********
***************************
***************************
***************************
***************************
***************************
***************************
***************************
***************************
***************************

์ฒ˜์Œ์—๋Š” ์ด๋Ÿฐ ๋ชจ์–‘์œผ๋กœ ๋ณ„์„ ์‚ฝ์ž…ํ•œ๋‹ค์Œ

*********
*********
*********
***   ***
***   ***
***   ***
*********
*********
*********

์ด ๋„ํ˜•์„ ๊ณต๋ฐฑ์ด ๋ชจ์—ฌ์žˆ๋Š” ๊ฐ€์šด๋ฐ๋ฅผ ์ œ์™ธํ•˜๊ณ  ๋ถ™์—ฌ

***************************
***************************
***************************
***   ******   ******   ***
***   ******   ******   ***
***   ******   ******   ***
***************************
***************************
***************************
*********         *********
*********         *********
*********         *********
***   ***         ***   ***
***   ***         ***   ***
***   ***         ***   ***
*********         *********
*********         *********
*********         *********
***************************
***************************
***************************
***   ******   ******   ***
***   ******   ******   ***
***   ******   ******   ***
***************************
***************************
***************************

์ด๋Ÿฐ ๋ฌธ์–‘์„ ๋งŒ๋“ค์–ด๋‚ด๊ณ  ๋˜ ๋” ์ž‘์€ ๋ฌธ์–‘์„ ๋งŒ๋“ค๊ณ  ์œ„์™€ ๊ฐ™์€ ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•˜๋„๋ก ํ•œ๋‹ค.

์†Œ์Šค

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

int n,cursor[2]={0,0}; // '*' = side_length , ' ' = side_length / 3, cursor = {x,y}
bool arr [6561][6561],src [6561][6561];
void set(int side_length)
{
	///////// arr ๋ฐฐ์—ด ์ดˆ๊ธฐํ™” /////////
	if(side_length == n)
		for(int i=0; i<n; i++)
			memset(arr[i],true,sizeof(bool)*n);
	///////// src ๋ฐฐ์—ด ์„ค์ • //////////
	for(int i=0; i<side_length; i++)	//๋ณ„ ์ฐ๊ธฐ
		memset(src+i,true,side_length);
	int center = side_length/3;
	for(int i=center; i<center+(side_length/3); i++)  //๋นˆ์นธ ์ถ”๊ฐ€
		memset(src[i]+(side_length/3),false,center);
	/////////src ์—์„œ ๋งŒ๋“  ํŒจํ„ด arr๋กœ ๊ทœ์น™์— ๋งž์ถฐ ๋ณต์‚ฌ///////////
	for(cursor[1] = 0; cursor[1]<n; cursor[1]+=side_length)
		for(cursor[0] = 0; cursor[0]<n; cursor[0] += side_length)
			for(int i=0; i<side_length; i++)
				if(*(arr[cursor[1]+i]+cursor[0]) != false)
					memcpy(arr[cursor[1]+i]+cursor[0],src[i],sizeof(bool)*side_length);		
	if(side_length > 3)
		set(side_length/3);
}
int main()
{
	scanf("%d",&n);
	set(n);
	for(int i=0; i<n; i++) // ํ…Œ์ŠคํŠธ ์ถœ๋ ฅ
	{
		for(int j=0; j<n; j++)
			printf("%c",arr[i][j] ? '*':' ');
		printf("\n");
	}
	return 0;
}

๋‚ด ์†Œ์Šค ๊ธฐ์ค€์œผ๋กœ src๋ฐฐ์—ด์— ์ ์  ์ž‘์•„์ง€๋Š” ๋ฌธ์–‘์„ ๋งŒ๋“ค๊ณ  ๊ทธ ๋ฌธ์–‘๋“ค์„ arr๋ฐฐ์—ด์— ๋ถ™์—ฌ ๋ฌธ์–‘์„ ๋งŒ๋“ค๋„๋ก ํ•˜์˜€๋‹ค.