BlockChain

저번에 탈출했던 미로를 리스트 스택으로 바꾸어 탈출하는 미션이다. 

정답 코드

#include <iostream>
#define MAZE_SIZE 10
#define STACK_MAX_SIZE 1000
using namespace std;

enum EMAZETYPE { PATH, WALL, VISIT, BACK }; // 0,1,2,3

int Maze[MAZE_SIZE][MAZE_SIZE] = {
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 1, 0, 1, 1, 0, 1},
{1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 1, 0, 1},
{1, 0, 1, 1, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 0, 1, 1, 1, 1, 1},
{1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
{1, 0, 1, 1, 1, 1, 0, 1, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
};


struct Position
{
    int x, y;
};

struct Direction
{
    int dx[4] = { -1,0,1,0 };
    int dy[4] = { 0,1,0,-1 };
};


struct Node
{
    Position data;
    Node* pNext;
    Node* TopPointer;

    void init_stack()
    {
        TopPointer = nullptr;
    }

    int is_emptied()
    {
        return (TopPointer == nullptr);
    }

    void Push(Position data)
    {
        // 동적할당 했고, 
        Node* m = (Node*)malloc(sizeof(Node));

        m->data = data;
        m->pNext = TopPointer;
        TopPointer = m;
    }

    void Pop()
    {
        if (is_emptied())
        {
            exit(1);
        }
        Node* tmp = TopPointer;
        TopPointer = tmp->pNext;
        delete tmp;
        // free(TopPointer--);
        // TopPointer--;
    }

    Position Peek()
    {
        return TopPointer->data;
    }

    void  MazeDraw()
    {
        for (size_t i = 0; i < MAZE_SIZE; i++)
        {
            for (size_t j = 0; j < MAZE_SIZE; j++)
            {
                switch (Maze[i][j])
                {
                case PATH:
                    cout << " ";
                    break;
                case WALL:
                    cout << "#";
                    break;
                case VISIT:
                    cout << "V";
                    break;
                case BACK:
                    cout << "B";
                    break;
                }
            }
            cout << endl;
        }

    }
};

int main()
{
    Node stack;
    Direction d;

    stack.init_stack();
    stack.Push({ 1, 1 });



    while (!stack.is_emptied())
    {
        // stack 상단 뽑기
        int x = stack.Peek().x;
        //cout << x << " ";
        int y = stack.Peek().y;
        //cout << y << " ";

        if (x == MAZE_SIZE - 2 && y == MAZE_SIZE - 2)
        {
            Maze[x][y] = VISIT;
            break;
        }

        if (Maze[x][y] == PATH) {
            Maze[x][y] = VISIT;
        }
        else if (Maze[x][y] == VISIT) {
            Maze[x][y] = BACK;
        }

        bool flag = false;

        for (size_t i = 0; i < 4; i++)
        {
            // 4방향 좌표 반복으로 체크
            int nx = x + d.dx[i];
            int ny = y + d.dy[i];

            // 범위 이상 벗어나지 않거나 메이즈가 이동가능한 0 이면 실행
            if ((0 <= nx && nx < MAZE_SIZE) && (0 <= ny && ny < MAZE_SIZE) && Maze[nx][ny] == PATH)
            {
                // 이동 가능하다면 스택 추가 
                stack.Push({ nx,ny });
                // 이동 가능한지 체크 플래그 설정 
                flag = true;

                break;
            }
        }
        // 플래그가 false 라면 B로 만들어줌
        if (!flag)
        {
            Maze[x][y] = BACK;
            // B로 만든 후에 pop으로 최상단 빼기 
            stack.Pop();
        }
    }

    stack.MazeDraw();
    return 0;
}
// 리스트스택 미로

문제 

스택 미로 로직 생각 해보기 

상 우 하 좌의 좌표를 

      0  1  2  3

dx   -1 0 1  0

dy    0  1 0 -1

로 두고 direction의 좌표를 탐색하는 방식으로 스택에 쌓음. 

만약 이동가능한 path 라면 visit로 바꾸고 visit라면 back으로 바꿈

if(4방향 반복)

if(범위이상 벗어나지 않거나 메이즈가 이동가능한 path 이면 실행)

이동 가능하다면 stack.push

이동 가능한 지 플래그 true

이동 불가능 플래그라면 maze[x][y]를 back 으로 변경 후 stack.pop

범위이상 

정답 코드

#include <iostream>
#define MAZE_SIZE 10
#define STACK_MAX_SIZE 1000
using namespace std;

enum EMAZETYPE { PATH, WALL, VISIT, BACK }; // 0,1,2,3

int Maze[MAZE_SIZE][MAZE_SIZE] = {
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 1, 0, 1, 1, 0, 1},
{1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 1, 0, 1},
{1, 0, 1, 1, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 0, 1, 1, 1, 1, 1},
{1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
{1, 0, 1, 1, 1, 1, 0, 1, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
};


struct Position
{
    int x, y;
};

struct Direction
{
    int dx[4] = { -1,0,1,0 };
    int dy[4] = { 0,1,0,-1 };
};


struct MyStack
{
    Position Array[STACK_MAX_SIZE];
    int nTopIndex;
    int stackSize = 0;

    void init_stack()
    {
        nTopIndex = -1;
    }

    int is_empty()
    {
        return (nTopIndex == -1);
    }

    int is_full()
    {
        return (nTopIndex == STACK_MAX_SIZE - 1);
    }

    void Push(Position data)
    {
        if (is_full())
        {
            return;
        }
        //nTopIndex++;
        stackSize++;
        Array[++nTopIndex] = data;
    }

    Position Pop()
    {
        if (is_empty())
        {
            exit(1);
        }
        return Array[nTopIndex--];
    }

    Position Peek()
    {
        return Array[nTopIndex];
    }

    void  MazeDraw()
    {
        for (size_t i = 0; i < MAZE_SIZE; i++)
        {
            for (size_t j = 0; j < MAZE_SIZE; j++)
            {
                switch (Maze[i][j])
                {
                case PATH:
                    cout << " ";
                    break;
                case WALL:
                    cout << "#";
                    break;
                case VISIT:
                    cout << "V";
                    break;
                case BACK:
                    cout << "B";
                    break;
                }
            }
            cout << endl;
        }

    }
};

int main()
{
    MyStack stack;
    Direction d;

    stack.init_stack();
    stack.Push({ 1, 1 });

    while (!stack.is_empty())
    {
        // stack 상단 뽑기
        int x = stack.Peek().x;
        int y = stack.Peek().y;

        if (x == MAZE_SIZE - 2 && y == MAZE_SIZE - 2)
        {
            Maze[x][y] = VISIT;
            break;
        }

        if (Maze[x][y] == PATH) {
            Maze[x][y] = VISIT;
        }
        else if (Maze[x][y] == VISIT) {
            Maze[x][y] = BACK;
        }

        bool flag = false;

        for (size_t i = 0; i < 4; i++)
        {
            // 4방향 좌표 반복으로 체크
            int nx = x + d.dx[i];
            int ny = y + d.dy[i];

            // 범위 이상 벗어나지 않거나 메이즈가 이동가능한 0 이면 실행
            if ((0 <= nx && nx < MAZE_SIZE) && (0 <= ny && ny < MAZE_SIZE) && Maze[nx][ny] == PATH)
            {
                // 이동 가능하다면 스택 추가 
                stack.Push({ nx,ny });
                // 이동 가능한지 체크 플래그 설정 
                flag = true;

                break;
            }
        }
        // 플래그가 false 라면 B로 만들어줌
        if (!flag)
        {
            Maze[x][y] = BACK;
            // B로 만든 후에 pop으로 최상단 빼기 
            stack.Pop();
        }
    }

    stack.MazeDraw();
    return 0;
}
// 하... 겨우 했다.. 미로 갇히지 말자..