C/C++ 재귀함수를 사용하지 않고 페인트칠하기!

안녕하세요, IT디자이너입니다. 

 

이번 포스팅은 저번 포스팅에 재귀함수를 활용하여 페인팅하는 프로그램을 재귀함수를 사용하지 않고 구현하도록 하겠습니다. 

 

사실, 모든 재귀함수를 사용하는 로직은 재귀함수를 사용하지 않고 구현할 수 있다고 하여도 과언이 아닙니다.

 

그래서!! 저번에 구현하였던 재귀함수 코드를 반복문으로 변경하도록 하겠습니다. 

 

사실 이번에는 스택(Stack)이라는 (First In Last Out)형태의 자료구조를 활용하여야 합니다. 

 

 

먼저 활용할 스택의 소스코드를 설명드리도록 하겠습니다. 

 

#include <iostream>

#define MAX_STACK_SIZE 100 // 스택의 사이즈

typedef struct screen { // 스택에 활용할 구조체입니다.
    int height;
    int width;
}Screen;

Screen stack[MAX_STACK_SIZE]; // 스택 생성
int top = -1; // 스택의 ebp


bool IsEmpty() { // 스택이 비었는지 확인하는 함수
    if (top < 0)
        return true;
    else
        return false;
}

bool IsFull() { // 스택이 꽉 찼는지 확인하는 함수
    if (top >= MAX_STACK_SIZE - 1)
        return true;
    else
        return false;
}
bool push(int widthVal,int heigthVal) {
    if (IsFull() == true)
        return false;
    else {
        stack[++top] = { heigthVal,widthVal };
        return true;
    }
}

bool pop(int &heightVal,int &widthVal) { // 스택의 높이를 낮추는 함수입니다. 
    if (IsEmpty() == true)
        return false;
    else {
        heightVal = stack[top].height;
        widthVal = stack[top--].width;
        return false;  
    }
}

bool espView(int& heightVal, int& widthVal) { // 현재 top에 위치한 스택의 값을 보는 함수입니다.
    if (IsEmpty() == true)
        return false;
    else {
        heightVal = stack[top].height;
        widthVal = stack[top].width;
        return true;
    }
}


int main() {

    int outHeight,outWidth;

    push(3,5);
    
    push(5,7);
    
    push(12,8);
    
    pop(outHeight, outWidth);
    printf("%d %d\n", outHeight, outWidth);

    pop(outHeight, outWidth);
    printf("%d %d\n", outHeight, outWidth);

    pop(outHeight, outWidth);
    printf("%d %d\n", outHeight, outWidth);


    return 0;
}

 

위의 자료구조를 확인해보면 동일한 공통점을 찾아보실 수 있으실 겁니다. 바로 함수의 반환형이 모두 bool 형태입니다. 

 

모든 자료구조는 함수 내에서 출력하는 것이 아닌 함수 외부에서 출력을 하며 오로지 성공여부만 반환합니다.

 

만약 저번 재귀함수를 보았다면, 제가 알려드린 스택의 자료구조를 활용하여 분명 재귀함수를 사용하지 않고 구현하실 수 있을 겁니다.!!

 

꼭 혼자서 풀어보고 답을 확인해주세요~~!!!!

 

답 

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <Windows.h>
#include <string.h>

#define SCREEN_WIDTH 18 // 맵의 가로
#define SCREEN_HEIGHT 9 // 맵의 높이

#define MAX_STACK_SIZE 10000 // 스택의 최대 사이즈

typedef struct screen { // 스택 자료구조의 구조체
    int height; 
    int width;
}Screen;

Screen stack[MAX_STACK_SIZE]; //스택 생성
int top = -1; // 스택의 top

bool IsEmpty() { // 스택이 비었는지 확인하는 함수
    if (top < 0)
        return true;
    else
        return false;
}

bool IsFull() { // 스택이 꽉 찼는지 확인하는 함수
    if (top >= MAX_STACK_SIZE - 1)
        return true;
    else
        return false;
}

bool push(int heigthVal,int widthVal) { // 스택에 값을 넣는 함수
    if (IsFull() == true)
        return false;
    else {
        stack[++top] = { heigthVal,widthVal };
        
        return true;
    }
}

bool pop() { // 스택에 값을 빼는 함수
    if (IsEmpty() == true)
        return false;
    else {
        top--; // 메모리를 비우는 것이 아닌 top의 높이만 바꾸면 된다.
        return true;
    }
}

bool espView(int& heightVal, int& widthVal) { // 현재 top이 가리키는 값을 얻는 함수입니다.
    if (IsEmpty() == true)
        return false;
    else {
        heightVal = stack[top].height;
        widthVal = stack[top].width;
        return true;
    }
}

void DrawBuffer(); // 맵을 그리는 함수입니다.

void PaintChar(int iX, int iY); // 0을 '.'로 바꾸는 함수입니다. 

char Original[SCREEN_HEIGHT][SCREEN_WIDTH] = {
    {' ','0','0',' ',' ',' ',' ','0','0','0',' ',' ',' ',' ',' ',' ','0','0'},
    {' ','0','0','0','0','0','0','0','0','0','0','0','0',' ',' ','0','0','0'},
    {'0','0','0','0','0',' ',' ','0','0','0','0','0','0',' ',' ','0','0','0'},
    {'0','0','0','0',' ',' ',' ','0','0','0','0','0','0','0','0','0','0','0'},
    {'0','0','0',' ','0',' ','0','0','0','0','0','0','0','0','0','0','0','0'},
    {'0','0',' ',' ','0',' ','0','0','0','0','0','0','0','0','0','0','0',' '},
    {'0','0',' ','0','0',' ','0','0','0','0','0','0','0','0','0','0',' ',' '},
    {' ','0',' ',' ','0',' ','0','0','0','0','0','0','0','0','0',' ',' ',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ','0','0','0','0','0','0',' ',' ',' ',' '}
};

char Buffer[SCREEN_HEIGHT][SCREEN_WIDTH];


int main()  // main코드는 저번 포스팅의 재귀함수 소스코드와 동일합니다.
{
    int iCountHeight, iCountWidth;

    while (1) {
        for (iCountHeight = 0; iCountHeight < SCREEN_HEIGHT; iCountHeight++) {
            for (iCountWidth = 0; iCountWidth < SCREEN_WIDTH; iCountWidth++) {
                Buffer[iCountHeight][iCountWidth] = Original[iCountHeight][iCountWidth];
            }
        }

        DrawBuffer();
        Sleep(3000);

        PaintChar(10, 3);
        Sleep(3000);

    }


}

void DrawBuffer() { // 저번 포스팅의 재귀함수 코드와 동일합니다.
    
    system("cls");

    for (int iCountHeight = 0; iCountHeight < SCREEN_HEIGHT; iCountHeight++) {
        for (int iCountWidth = 0; iCountWidth < SCREEN_WIDTH; iCountWidth++) {
            printf_s("%c", Buffer[iCountHeight][iCountWidth]);
        }
        printf_s("\n");
    }
}

void PaintChar(int widthX, int heightY) {
    
    push(heightY, widthX); // 첫 위치를 push합니다.

    int check = 0; // 값이 4 이상이면 왼쪽 오른쪽 위 아래에 0이 없을 경우이다.

    int stackWidth = widthX;
    int stackHeight = heightY;
    while (1) {

        while (1) {

            espView(stackHeight, stackWidth); // 현재 top의 값을 출력 
            push(stackHeight, --stackWidth); // 좌표를 왼쪽으로 하여 push!
            espView(stackHeight, stackWidth); // 다시 현재 top의 위치를 출력

            if (stackWidth < 0) { // 왼쪽으로 -- 하였을 때 0 미만이면 pop!
                check++; // 체크!
                pop();
                break;
            }

			//현재 위치가 이미 '.'으로 바뀌었거나 ' ' 이면은 pop!!!
            if (Buffer[stackHeight][stackWidth] == '.' || Buffer[stackHeight][stackWidth] == ' ') {
                check++;
                pop();
                break;
            }

            check = 0; // if문으로 break가 되지 않았을 경우 0으로 대입!
            Buffer[stackHeight][stackWidth] = '.';
            DrawBuffer();
        }

        while (1) {

            espView(stackHeight, stackWidth);
            push(stackHeight, ++stackWidth);
            espView(stackHeight, stackWidth);


            if (stackWidth >= SCREEN_WIDTH) {
                check++;
                pop();
                break;
            }


            if (Buffer[stackHeight][stackWidth] == '.' || Buffer[stackHeight][stackWidth] == ' ') {
                check++;
                pop();
                break;
            }
            check = 0;
            Buffer[stackHeight][stackWidth] = '.';

            DrawBuffer();
        }

        while (1) {

            espView(stackHeight, stackWidth);
            push(--stackHeight, stackWidth);
            espView(stackHeight, stackWidth);

            if (stackHeight < 0) {
                check++;
                pop();
                break;
            }

            if (Buffer[stackHeight][stackWidth] == '.' || Buffer[stackHeight][stackWidth] == ' ') {
                check++;
                pop();
                break;
            }

            check = 0;
            Buffer[stackHeight][stackWidth] = '.';
            
            DrawBuffer();
        }

        
        while (1) {

            espView(stackHeight, stackWidth);
            push(++stackHeight, stackWidth);
            espView(stackHeight, stackWidth);

            if (stackHeight >= SCREEN_HEIGHT) {
                check++;
                pop();
                break;
            }

            if (Buffer[stackHeight][stackWidth] == '.' || Buffer[stackHeight][stackWidth] == ' ') {
                check++;
                pop();
                break;
            }

            check = 0;
            Buffer[stackHeight][stackWidth] = '.'; 
            DrawBuffer();
        }

        if (check >= 4) { // 4 이상이면 pop!!
            pop();
        }
        
        if(isEmpty()=true){ // 스택 다 소진시 break!
        	break;
		}
    }
}

 

이렇게 자료구조를 활용하여 재귀함수를 사용하지 않고 구현해보았습니다. !!!!!

 

사실 재귀함수는 복잡하며, 계속해서 스택 메모리의 매개변수를 채워넣기 때문에 메모리 낭비도 심합니다.!

 

또한 재귀함수는 오류를 잡기 어려운 코드이기 때문에 되도록이면 피하는 것이 좋은 코드입니다.

 

---

이상 IT디자이너였습니다.!!

 

 

감사합니다.!!!!!!!!!