c++로 작성한 미로 클래스

자료구조 프로그래밍 과목을 배우면서 c++로 작성한 미로 클래스입니다.

maze.in

maze.in2

maze.cpp

#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);

        bool isEmpty() const;

        T &Top() const;

        void Push(const T &item);

        T &Pop();

};

 

 

template <typename T>

Stack<T>::Stack(int stackCapacity) :capacity(stackCapacity)

{

        if (capacity < 1)

               throw "Stack capcity must be >0";

        stack = new T[capacity];

        top = -1;

}

 

template <typename T>

inline bool Stack<T>::isEmpty() const

{

        return top == -1;

}

 

template <typename T>

inline T &Stack<T>::Top() const

{

        if(isEmpty())

               throw "Stack is empty";

        return stack[top];

}

 

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;

}

 

template <typename T>

void Stack<T>::Push(const T &x)

{

        if (top == capacity - 1)

        {

               ChangeSize1D(stack, capacity, 2 * capacity);

               capacity *= 2;

        }

        stack[++top] = x;

}

 

template <typename T>

T &Stack<T>::Pop()

{

        T &del = stack[top];

        if (isEmpty())

               throw "Stack is empty. Cannot delete.";

        stack[top--].~T();

        return del;

}

 

const int MAXSIZE = 100;

bool maze[MAXSIZE + 2][MAXSIZE + 2]; //테두리를 위해 MAXSIZE+2

bool mark[MAXSIZE + 2][MAXSIZE + 2] = { 0 }; //방문한 곳을 표시

 

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

 

struct offsets

{

        int a, b;

};

 

offsets moveDir[8] = { {-1, 0},{-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} }; //구조체 배열(directions에 대한 정의)

 

struct Items

{

        int x, y, dir; //x축, y축, 방향

        Items(int xx = 0, int yy = 0, int dd = 0) :x(xx), y(yy), dir(dd)

        {

        }

};

 

template <typename T>

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

{

        //순서대로 출력하려면 스택을 두개 사용하여 큐처럼 작동하도록 해야합니다

        //스택:LIFO, 큐:FIFO

        Stack<T> temp;

        while (!s.isEmpty())

               temp.Push(s.Pop());

        while (!temp.isEmpty())

               os << "->" << temp.Pop();

        return os;

}

 

ostream &operator<<(ostream &os, Items &item)

{

        static int count = 0;

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

        count++;

        //5개 출력마다 한칸 띄운다

        if ((count % 5) == 0)

               os << endl;

        return os;

}

 

void Path(const int m, const int p)

{

        mark[1][1] = 1;

        Stack<Items> stack(m*p);

        Items temp(1, 1, E);

        stack.Push(temp); //(1, 1, E)를 우선 Push

 

        while (!stack.isEmpty()) //스택이 빌 때까지

        {

               temp = stack.Top();

               stack.Pop();

               int i = temp.x;

               int j = temp.y;

               int d = temp.dir;

               while (d < 8) //모든방향으로 시도해본다

               {

                       int g = i + moveDir[d].a;

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

                       if ((g == m) && (h == p)) //목적지에 도착하면

                       {

                              int number = 0;

                              cout << stack;

                              temp.x = i;

                              temp.y = j;

                              cout << "->" << temp;

                              temp.x = m;

                              temp.y = p;

                              cout << "->" << temp << endl;

                              for (int i = 1; i < m + 1; i++)

                                      for (int j = 1; j < p + 1; j++)

                                              if (mark[i][j])

                                                     number++;

                              cout << endl << endl << "#nodes visited = "<< number <<" out of "<< 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;

                              stack.Push(temp);

                              i = g;

                              j = h;

                              d = N;

                       }

                       else

                              d++; //방향을 바꾼다

               }

        }

        cout << "No path in Maze" << endl;

}

 

void getdata(istream &is, int &m, int &p)

{

        is >> m >> p;

        //테두리를 벽으로 만든다

        for (int i = 0; i < m + 2; i++)

        {

               maze[i][0] = 1;

               maze[i][p + 1] = 1;

        }

        for (int j = 0; j < p + 2; j++)

        {

               maze[0][j] = 1;

               maze[m + 1][j] = 1;

        }

        //테두리 내에 있는 진짜 미로

        for (int i = 1; i <= m; i++)

               for (int j = 1; j <= p; j++)

                       is >> maze[i][j];

}

 

hw5.cpp

#include <iostream>

#include <fstream>

using namespace std;

 

void getdata(istream &, int &, int &);

void Path(int, int);

 

int main(int argc, char *argv[])

{

        int m, p; //m by p maze

        if (argc == 1) //미로 파일이 포함되지 않은 경우

               cerr << "Usage: " << argv[0] << " maze_data_file" << endl;

        else

        {

               ifstream is(argv[1]);

               if (!is) //미로파일이 존재하지 않는다면

               {

                       cerr << argv[1] << " does not exist" << endl;

                       return -1;

               }

               cout << "For maze datafile (" << argv[1] << ")" << endl;

               getdata(is, m, p);

               is.close();

               Path(m, p);

        }

        return 0;

}

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~