이번에는 이전 시간에 구현한 LinkedStack을 이용해 미로 탈출 알고리즘을 구현해 볼 것이다.

헤더 분석(이전의 Linked Stack과 비슷)

#ifndef _LINKED_STACK_
#define _LINKED_STACK_
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//여기서 Maze구조체 필요
typedef struct  StackNodeType
{
    int dx;
    int dy;
    char direction;
    struct StackNodeType* pLink;
}   MapPosition;
typedef struct LinkedStackType
{
    int currentElementCount;
    MapPosition* pTopElement;
} LinkedStack;
//////////////////maze구조체
LinkedStack* createLinkedStack();
MapPosition* popLSMapPosition(LinkedStack* pStack);
MapPosition* peekLSMapPosition(LinkedStack* pStack);
void                    deleteLinkedStack(LinkedStack* pStack);
int                     isLinkedStackFull(LinkedStack* pStack);
int                     isLinkedStackEmpty(LinkedStack* pStack);
///////maze

#endif
#ifndef _COMMON_STACK_DEF_
#define _COMMON_STACK_DEF_
#define TRUE        1
#define FALSE       0
#define ERROR       -1
#define HEIGHT      8
#define WIDTH       8
#endif

이번에는 StackNode 대신에 방문한 좌표와 방향, 다음 노드를 가리킬 수 있는 포인터를 멤버 변수로 가지는 MapPosition을 구조체로 선언해 주었다. dx, dy는 방문한 maze의 좌표이며, direction은 동서남북 중 하나이다. 또한 maze의 WIDTH와 HEIGHT를 헤더에 define해 주었다.

전역변수

int     direction[4][2] = { 1, 0, 0, -1, -1, 0, 0, 1 };
char    cardinal_point[4] = { 'S', 'W', 'N', 'E' };
int     mazeArray[HEIGHT][WIDTH] =
{
    0, 0, 1, 1, 1, 1, 1, 1,
    1, 0, 0, 0, 0, 0, 0, 1,
    1, 1, 1, 0, 1, 1, 1, 1,
    1, 1, 1, 0, 1, 1, 1, 1,
    1, 0, 0, 0, 0, 0, 0, 1,
    1, 0, 1, 1, 1, 1, 1, 1,
    1, 0, 0, 0, 0, 0, 0, 0,
    1, 1, 1, 1, 1, 1, 1, 0
};

이 코드에서 쓰이는 전역변수는 총 3가지이다.

• 방향을 나타내려면 x와 y좌표가 있어야 하고, 대각선을 뺀 위 아래 왼쪽 오른쪽 방향만 쓰이기에 4x2배열로 방향을 선언해 주었다.
• cardinal_point는 방위를 나타내며, for문으로 direction이 돌기 때문에 cardinal_point 또한 4칸으로 선언해 주었다.
• maze의 map은 이차원 배열로 선언되어 있으며, 갈 수 있는 빈 공간은 0으로, 갈 수 없는 벽은 1로 선언했다.

이제 linkedstack에서 구현한 함수들과 다른 점을 위주로 포스팅 할 것이다.

createLinkedStack 함수 구현

LinkedStack* createLinkedStack()
{
    LinkedStack* pStack = NULL;
    pStack = (LinkedStack*)malloc(sizeof(LinkedStack));
    if (pStack == NULL)
    {
        printf("[error] malloc failure : pStack\\n");
        return (NULL);
    }
    memset(pStack, 0, sizeof(LinkedStack));
    return (pStack);
}

linked stack과 다른 점 없음.

pushLSMapPosition 함수 구현

int     pushLSMapPosition(LinkedStack* pStack, MapPosition data)
{
    MapPosition* ps = NULL;
    if (pStack == NULL)
    {
        printf("[error] Null parameter : pStack\\n");
        return (FALSE);
    }
    ps = (MapPosition*)malloc(sizeof(MapPosition));
    if (ps == NULL)
    {
        printf("[error] malloc failure : ps\\n");
        return (FALSE);
        //malloc실패
    }
    *ps = data;
    ps->pLink = pStack->pTopElement;
    pStack->pTopElement = ps;
    pStack->currentElementCount++;
    return (TRUE);
}

linkedStack과 다른 점은 LinkedStackNode pNode 대신 MapPosition ps를 선언하고 여기에 data를 넣었다는 점이다. 넣는 순서 등은 모두 linkedStack과 같다.

popLSMapPosition 함수 구현

MapPosition* popLSMapPosition(LinkedStack* pStack)
{
    MapPosition* delNode = NULL;
    if (pStack == NULL)
    {
        printf("[error] Null parameter : pStack\\n");
        return (FALSE);//각자
    }
    if (isLinkedStackEmpty(pStack) == TRUE)
    {
        printf("[error] Stack Underflow\\n");
        return (delNode);//각자
    }
    delNode = pStack->pTopElement;
    pStack->pTopElement = delNode->pLink;
    delNode->pLink = NULL; //어차피 반환할 노드니까 pLink를 널로.
    pStack->currentElementCount--;
    return (delNode);
}

LinkedStack과 다른 점은 delNode를 MapPosition의 형식으로 선언했다는 점이며, 나머지는 모두 linkedStack과 같다.