C++ Fundamentals of Data Structures(C++ 자료구조론) 3.5 미로 예제

미로 코드가 제시되어있지 않고 딱히 연습문제에서도 풀라는 문제가 없었기 때문에 직접 작성해봤습니다!

#include <iostream>

#include <algorithm>

using namespace std;

 

//앞서 정의한 Stack

template <typename T>

class Stack

{

private:

        T *stack; //스택배열

        int top; //제일 마지막에 삽입된 원소

        int capacity; //배열 크기

public:

        Stack(int stackCapacity = 10) :capacity(stackCapacity)

        {

               if (capacity < 1)

                       throw "Stack capacity must be >0";

               stack = new T[capacity];

               top = -1;

        }

 

        ~Stack()

        {

               delete[]stack;

        }

 

        bool IsEmpty() const

        {

               return top == -1;

        }

 

        T &Top() const

        {

               if (IsEmpty())

                       throw "Stack is empty";

               return stack[top];

        }

 

        void Push(const T &x)

        {

               if (top == capacity - 1)

               {

                       ChangeSize1D(stack, capacity, 2 * capacity);

                       capacity *= 2;

               }

               stack[++top] = x;

        }

 

        void Pop()

        {

               if (IsEmpty())

                       throw "Stack is empty. Can't Delete";

               stack[top--].~T(); //destructor for T(처음보는 활용법)

        }

        template <typename T> //이걸 추가하지 않으면 basic operator<< 라고 여겨져 오류가 납니다

        friend ostream &operator<<(ostream &os, Stack<T> &s); //출력

};

 

template <typename T>

ostream &operator<<(ostream &os, Stack<T> &s)

{

        os << "현재 Top: " << s.Top() << endl;

        for (int i = 0; i <= s.top; i++)

               os << i + 1 << ": " << s.stack[i] << endl;

        return os;

}

 

template <typename T>

void ChangeSize1D(T *&a, const int oldSize, const int newSize)

{

        if (newSize < 0)

               throw "New length must be >=0";

 

        T *temp = new T[newSize];

        int number = min(oldSize, newSize);

        copy(a, a + number, temp);

        delete[]a;

        a = temp;

}

 

typedef struct

{

        int a, b;

}offsets;

 

enum directions { N, NE, E, SE, S, SW, W, NW };  //방향

 

offsets moveto[8] = { { -1,0 },{ -1,1 },{ 0,1 },{ 1, 1 },{ 1, 0 },{ 1, -1 },{ 0,-1 },{ -1, -1 } }; //directions를 좌표로 표현

 

struct Items

{

        int x, y, dir;

        Items()

        {

               //디폴트

        };

        Items(int a, int b, int d)

        {

               x = a;

               y = b;

               dir = d;

        }

};

 

ostream &operator<<(ostream &os, Items &item) //Stack<Item>을 위한 추가전인 << 연산자

{

        os << item.x << ", " << item.y << ", ";

        switch (item.dir)

        {

        case 1:

               cout << "N";

               break;

        case 2:

               cout << "NE";

               break;

        case 3:

               cout << "E";

               break;

        case 4:

               cout << "SE";

               break;

        case 5:

               cout << "S";

               break;

        case 6:

               cout << "SW";

               break;

        case 7:

               cout << "W";

               break;

        case 8:

               cout << "NW";

        }

        return os;

}

 

int mark[13][17] = { 0, }; //갔던 지점 표기

int maze[13][17] = { //Figure 3.11

        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },

        { 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1 },

        { 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1 },

        { 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1 },

        { 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1 },

        { 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 },

        { 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1 },

        { 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1 },

        { 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1 },

        { 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1 },

        { 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1 },

        { 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1 },

        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },

};

 

void Path() //이미 열과 오가 정해졌으므로 const int m. const int p 생략 가능

{

        //(Program 3.16)

        int m = 11; //벽은 제외하기 때문에 -2

        int p = 15; //벽은 제외하기 때문에 -2

 

        //1, 1에서 시작(벽 이후부터)

        mark[1][1] = 1;

        Stack<Items> stack(m*p);

        Items temp(1, 1, E);

        stack.Push(temp);

 

        while (!stack.IsEmpty())

        {

               temp = stack.Top();

               stack.Pop();

               int i = temp.x;

               int j = temp.y;

               int d = temp.dir;

               //cout << "d: " << d << endl;

               while (d < 8) //방향을 한번씩 해본다

               {

                       int g = i + moveto[d].a; //전진

                       int h = j + moveto[d].b;

                       //cout << "g: " << g << "\th: " << h << endl;

                       if ((g == m) && (h == p)) //탈출에 성공!

                       {

                              cout << stack;

                              cout <<"탈출직전 좌표: "<< i << " " << j << endl; //탈출하기 전 마지막 좌표

                              cout <<"탈출한 좌표: "<<  m << " " << p << endl;

                              return;

                       }

                       if ((!maze[g][h]) && (!mark[g][h])) //밟아보지 못했던 좌표일시

                       {

                              mark[g][h] = 1; //밟았다고 표시

                              temp.x = i; //혹시 모르니까 전에 있었던 좌표를 저장

                              temp.y = j;

                              temp.dir = d + 1; //만약 막다른길이여서 돌아왔을 시 다시 새로운 방향으로 가기 위해 d+1

 

                              stack.Push(temp);

                              i = g;

                              j = h;

                              d = N;

                       }

                       else

                              d++; //다른 방향으로 시도

               }

        }

        cout << "미로에 경로가 없습니다" << endl;

}

 

int main(void)

{

        cout << "미로 출력" << endl;

        for (int i = 0; i < 13; i++)

        {

               for (int j = 0; j < 17; j++)

                       cout << maze[i][j] << " ";

               cout << endl;

        }

        cout << endl;

        cout << "좌표 읽는법: (가로, 세로, 방향)" << endl;

        //cout << "방향:  1: N, 2: NE, 3: E, 4: SE, 5: S, 6: SW, 7: W, 8: NW " << endl << endl;

        Path();

        return 0;

}

[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서, https://kldp.org/node/134678, https://kldp.org/node/151431, http://blog.naver.com/PostView.nhn?blogId=ggaddr&logNo=20120631647

*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.

*많은 자료들을 참고하고 나서야 제대로 풀 수 있었습니다.