[자료구조] 03. Stack Flood Fill 예제 (C언어)

Stack 예제 중에서 Flood Fill에 대한 예제가 참 유명하다.

나중에 최적화 알고리즘을 사용하여 Application에 적용할수 있기 때문에

주요 Source 코드를 정리해 놓으면 요긴할것 같다.

 

/*-----------------------Include-----------------------*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>

/*-----------------------Define-----------------------*/
#define MAX_STACK_SIZE        100
#define TRUE 1
#define FALSE 0
#define WIDTH    7
#define HEIGHT    7

/*-----------------------Typedef-----------------------*/
typedef unsigned int uint32_t;
typedef int int32_t;
typedef unsigned char uint8_t;

typedef struct _Element
{
    int x;
    int y;
}Element;

typedef struct _Stack
{
    Element items[MAX_STACK_SIZE];
    int top;
}Stack;

/*---------------------- Static Function Header-----------------------*/


/*-----------------------Variable-----------------------*/
int map[HEIGHT][WIDTH] = {
    0, 0, 0, 0, 0 ,0 ,0,
    0, 1, 1, 1, 1 ,1 ,0,
    0, 1, 0, 0, 0 ,1 ,0,
    0, 1, 0, 0, 0 ,0 ,0,
    0, 1, 0, 0, 0 ,1 ,0,
    0, 1, 1, 1, 1 ,1 ,0,
    0, 0, 0, 0, 0 ,0 ,0
};

/*-----------------------Function-----------------------*/
uint8_t IsFull(Stack* pStack)
{
    if(pStack->top >=  MAX_STACK_SIZE -1)
    {
        return TRUE;
    }
    else
    {
        return FALSE;
    }
}

uint8_t IsEmpty(Stack* pStack)
{
    if(pStack->top == -1)
    {
        return TRUE;
    }
    else
    {
        return FALSE;
    }
}

void Push(Stack* pStack, Element item)
{
    if(IsFull(pStack)== TRUE)
    {
        printf("Stack is Full!\n");
    }
    else
    {
        pStack->items[++pStack->top] = item;
    }
}

Element Pop(Stack* pStack)
{
    Element item_temp;

    if(IsEmpty(pStack) == TRUE)
    {
        item_temp.x = -1;
        item_temp.y = -1;
        return item_temp;
    }
    else
    {
        return pStack->items[pStack->top--];
    }
}

void Initialization(Stack* pStack)
{
    pStack->top = -1;
}

Element get_element(int x, int y)
{
    Element temp;
    temp.x = x;
    temp.y = y;
    return temp;
}

void print_all(Stack* pStack)
{
    int i;

    if(pStack->top == -1)
    {
        printf("Stack is not exist!\n");
    }
    else
    {
        printf("Stack : ");
        for(i=0;i<=pStack->top;i++)
        {
            printf("%d,%d  ",pStack->items[i].x, pStack->items[i].y); 
        }
        printf("\n");
    }
}

void print_map(void)
{
    int i,j;

    for(i=0;i<HEIGHT;i++)
    {
        for(j=0;j<WIDTH;j++)
        {
            printf("%d ",map[i][j]);
        }
        printf("\n");
    }
}

int main(void)
{
    Stack my_stack;
    Element temp;

    Initialization(&my_stack);
    Push(&my_stack,get_element(0,0));
    print_all(&my_stack);

    while(IsEmpty(&my_stack)!=TRUE)
    {
        temp = Pop(&my_stack);
        if(map[temp.y][temp.x] == 1)
            continue;
        map[temp.y][temp.x] = 2;

        if(temp.y -1 >=0 && map[temp.y -1][temp.x] == 0)
            Push(&my_stack,get_element(temp.x, temp.y-1)); //up

        if(temp.y +1 < HEIGHT && map[temp.y +1][temp.x] == 0)
            Push(&my_stack,get_element(temp.x,temp.y +1)); //down

        if(temp.x -1  >=0 && map[temp.y][temp.x-1] == 0)
            Push(&my_stack,get_element(temp.x-1,temp.y)); //left

        if(temp.x+1 <WIDTH  && map[temp.y][temp.x+1] == 0)
            Push(&my_stack,get_element(temp.x+1,temp.y)); //right

        //Debugging
        system("cls");
        printf("Cell : %d, %d\n", temp.x, temp.y);
        print_all(&my_stack);
        print_map();
        printf("\n");
        (void)_getch();
    }
    return 0;
}

위와 같이 0으로 이루어진 공간에 물이 채워지듯 2로 변경이 되고 있는 것을 볼수 있다.