[BOJ] 2448. 별찍기11

문제보고오기

 

1. 프렉탈이란

 프렉탈이란 fractus 라는 쪼개지다라는 뜻을 갖는 라틴어에서 그 어원을 찾을 수 있습니다.

프렉탈은 위의 번개처럼 자기 자신을 닮은 모양이 끊임없이 반복되는 자기유사성을 띤다는 특징이 있습니다.

 

우리는 이러한 프렉탈 특징을 갖는 현상을 자연을 통해 손쉽게 확인해볼 수 있습니다.

그리고 몇몇 현상들은 재귀함수를 통해 손쉽게 구현할 수 있습니다.

 

이번 시간에는 프렉탈과 관련이 있는 BOJ 문제를 통해 재귀함수 사용을 익혀보도록 하겠습니다.

 

문제에서 주어진 삼각형의 모양을 자세히 살펴보면,

다음과 같이 큰 삼각형 안에 자신을 닮은 작은 삼각형이 

위, 왼쪽, 오른쪽으로 나뉘어 계속 반복 되고 있음을 알 수 있습니다.

 

2. 삼각형의 규칙과 재귀함수

큰 삼각형 안에 작은 삼각형이

1).위, 2).왼쪽, 3).오른쪽으로

총 3 영역으로 존재하고 있죠? 

그리고 이 1),2),3) 삼각형 안에서, 작은 위, 왼쪽, 오른쪽 삼각형들이 반복되고 있다는 것을 알 수 있습니다.

 

어떻게 하면 저런 삼각형을 그릴 수 있을까요?

 

삼각형의 높이와 꼭대기의 좌표를 재귀함수에게 알려주면 되지 않을까요?

 

void star(int h, int y, int x)
{
	//0.종료조건
 
	//1.위쪽 삼각형 그리기
 
	//2.왼쪽 삼각형 그리기
 
	//3. 오른쪽 삼각형 그리기
}

h는 높이, y,x는 arr[y][x] 배열의 행과 열의 좌표입니다.

 

y좌표가 x좌표보다 먼저 나온 이유는, 2차원 배열에서 원소접근 순서를 따르기 위함입니다.

2차원 배열은 행다음 열이 나오는 순서니까요~

따라서 우리가 흔히 쓰는 직교좌표계에서 가로 세로의 좌표는 x좌표지만배열에서는 arr[y][x]와 같이 열에 해당하는 원소가 됩니다.

 

그런데 재귀함수는 종료조건을 주지 않으면 무한루프에 빠져 스택이 터지는 오류를 보게 되실 겁니다!

마치 for문에서 for(int i = 0; ;i++) 을 실행하면 무한이 i가 증가하는 것처럼! 종료조건을 반드시 제시해줘야합니다.

3. 종료 조건

출처: 나무위키-재귀함수

 

종료조건이 없다면

“잘 들어보게~”

       “잘 들어보게~”

             “잘 들어보게~”

                    …

                      ..

                        .

처럼 교수님의 말씀이 끊임없이 출력이 되다가...... 스택이 넘치는 순간 스택오버플로우라는 에러를 띄우면서 프로그램이 종료됩니다.

 

현재처럼 종료조건을 주지 않은상태에서는 기존의 삼각형을 나누고 나누고.. 또 나누는 일을 끊임없이 계속 하게 됩니다.

그렇다면, 삼각형을 나누고 나누다 그만 나눠야 할때가 언제 일까요?

네, 바로

  *

 * *

*****

이런 모양이면 더이상 문제에서 찾아볼 수 없는 삼각형의 모양이 되기 때문에.

h(높이)가 3이 되면, 아래 코드와 같이 위의 모양을 출력 배열에 저장하고 return문을 사용하여 재귀를 마치도록 해야해요!

 

if (h == 3)
{							
	arr[y][x] = 42;										//  *			
	arr[y + 1][x - 1] = 42; arr[y + 1][x + 1] = '*';	// * *
	for (int i = 0; i < 5; i++)						//*****
	{
		arr[y + 2][x - 2 + i] = 42;
	}													
	return;
}

arr 는 char 형의 2차원 배열이며

지정 연산자 = 옆에 있는 42는 ‘*’ 문자의 ASCII 코드입니다.  아스키 코드로 하면 속도가 좀 더 빠르더라구요~

 

맨 처음 그려지는 별은 삼각형의 꼭대기기 때문에 y,x를 그대로 사용하고

그 다음 줄은 y가 1증가한 y+1에

x좌표가 왼쪽으로 한칸, 오른쪽으로 한 칸 이동한 것이기 때문에 x-1, x+1 이 됩니다.

마지막으로 밑변은 별이 5개 출력되어야 하고 기존의 y좌표로부터 2칸 떨어지고 x-2좌표로부터 i칸만큼 떨어져 있음을 알 수 있습니다.

이렇게 작성하시고

main 함수에서 star(3,꼭짓점좌표)를 입력하시면

arr 배열에 작은 삼각형이 들어갑니다.

 

4. h 가 3이 아닌 경우는 어떻게 할 것인가?

if(h==3)을 통해 높이가 3일 경우에는 삼각형을 그리고 return; 문을 사용하여 루틴이 종료되게 만들었습니다.

h!=3 인 경우는 어떻게 해야할까요?

else 문 안에 위,왼쪽, 오른쪽을 그리는 코드를 작성하고 안에서 재귀가 일어나게 해야겠죠?

따라서 다음과 같이 코드를 작성할 수 있습니다.

else
{
	star(h / 2, y, x);
	star(h / 2, y + h / 2, x - h / 2);
    star(h / 2, y + h / 2, x + h / 2);
}

1. star(); 높이는 절반, 꼭짓점 좌표는 그대로!
2. star(); 높이는 절반, 왼쪽에 있으므로 x좌표는 – 높이의 절반, y좌표는 기존 좌표 + 높이의 절반 
3. star(); 높이는 절반, 오른쪽에 있으므로 x좌표는 + 높이의 절반,  y좌표는 기존 좌표 + 높이의 절반 

 

5. 완성된 코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
char arr[3072][6143];
void star(int h, int y, int x)
{
	if (h == 3)
	{							
		arr[y][x] = 42;					//  *			
		arr[y + 1][x - 1] = 42; arr[y + 1][x + 1] = 42;	// * *
		for (int i = 0; i < 5; i++)			//*****
		{
			arr[y + 2][x - 2 + i] = '*';
		}													
		return;
	}
	else
	{
		star(h / 2, y, x);
		star(h / 2, y + h / 2, x - h / 2);
		star(h / 2, y + h / 2, x + h / 2);
	}
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 2*n-1; j++)
		{
			arr[i][j] = ' ';
		}
	}
	// 0행 n-1열을 꼭짓점으로 갖는 높이 n짜리 삼각형을 그려라.
	star(n, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 2 * n - 1; j++)
		{
			printf("%c", arr[i][j]);
		}
		printf("n");
	}
}