스택을 이용한 미로찾기 (Maze Problem ver. Stack) ​

#include "Maze.h"
#include <iostream>

int main(void)
{

 try
 {
  Maze* test;
  test = new Maze("maze.txt"); // txt file open
  int t = test->Find(1,1,13,13); // 길찾기. 
  // Find함수는 올바른 경로를 스택에 저장한다.
  // 올바른 경로가 존재하면 1을 반환하고 나머지 경우는 0을 반환한다.

  if (t==0)
   throw "No escape route.";

  test->Sol();// 스택에 저장된 경로를 보여준다(출력부분)
 }
 catch(char* e)
 {
  std::cout << e << "\n";
 }

 
}

#ifndef STACK_H
#define STACK_H

#include "Location.h"

class Stack
{

private:

 Location* stack;
 int top;
 int capacity;

public:

 Stack(int stackCapacity = 10);
 bool IsEmpty();
 Location Top();
 void Push(Location item);
 Location Pop();

};

#endif

#include "Stack.h"
#include "Location.h"

Stack::Stack(int stackCapacity)
{
 capacity = stackCapacity;
 if(capacity < 1)
  throw "Stack capacity must be > 0";
 stack = new Location[capacity];
 top = -1;
}

bool Stack::IsEmpty()
{
 return top == -1;
}

Location Stack::Top()
{
 if(IsEmpty())
  throw "Stack is empty"; 
 return stack[top];
}

void Stack::Push(Location x)
{
 if(top < capacity-1)
 {
  stack[++top] = x;
 } else {
  throw "Stack is full";
 }
}

Location Stack::Pop()
{
 if(IsEmpty())
  throw "Stack is empty";
 return stack[top--];

}

#ifndef LOCATION_H
#define LOCATION_H

class Location
{
private:
 int x;
 int y;
public:

 //클래스 동적배열을 사용하기 위해 기본 생성자를 사용한다.
 //Location();
 //Location(int xx, int yy);

 void Replace(int xx, int yy); // 객체에 x,y좌표를 재대입한다

 void Up(); // y->y-1
 void Down();// y->y+1
 void Left();// x->x-1
 void Right();// x->x+1

 int X();// 객체의 x를 출력
 int Y();// 객체의 y를 출력
 
 void Print(); // (x,y) 형식으로 출력
};

#endif

#include <iostream>
#include "Location.h"


void Location::Replace(int xx, int yy) { x=xx; y=yy; }
void Location::Up() { y--; }
void Location::Down() { y++; }
void Location::Left() { x--; }
void Location::Right() { x++; }
int Location::X() { return x; }
int Location::Y() { return y; }
void Location::Print() { std::cout << "(" << x << ", " << y << ")\n"; }

#ifndef MAZE_H
#define MAZE_H

#include "Stack.h"
#include "Location.h"

class Maze
{
private:
 
 int Map[15][15]; // 미로 정보를 저장할 이차원 배열
 Stack* Path; // 스택
 Location* P; // 임의의 좌표

public:

 Maze(char* str); // 생성자
 int IsBlock(Location* p); // p가 벽인지 길인지 확인하는 함수

 int Find(int x1,int y1,int x2,int y2); // 통합 길찾기 함수

 void Sol(); // 정답 출력

};

#endif

#include <iostream>
#include <fstream>
#include "Maze.h"

using  std::ifstream;

Maze::Maze(char* str)
{

 // 파일을 읽어서 배열에 저장한다
 ifstream in_file;
 in_file.open(str);
 int i,j;
 for(i=0;i<15;i++)
 {
//  in_file.getline(temp,30);
  for(j=0;j<15;j++)
  {
//   t=temp[j];
//   Map[i][j]=atoi(&t);
   in_file>>Map[i][j]; // 자동 형변환.. "1 "또는 "0 " 을 1,0 으로 변환
  }
 } 
 in_file.close();
 // 끝

 Path = new Stack(1000);

}
int Maze::IsBlock(Location* p)
{
 return Map[p->Y()][p->X()]; // 벽이면 1, 길이면 0을 반환
}
int Maze::Find(int x1,int y1,int x2,int y2)
{



 int result;
 Location T;
 P = new Location();
 P->Replace(x1,y1);
 
 if(Path->IsEmpty()) T.Replace(-2,-2);  // 처음 실행했을때(스택이 비어있을때) 허위값을 넣는다
 else T = Path->Top(); // T에 가장 최근 지나온 길의 좌표를 넣는다

 Path->Push(*P); // 스택에 현재 좌표를 대입한다

 if((x1==x2)&&(y1==y2)) return 1; // 시작점과 도착점이 같으면 1을 반환 (경로찾기 성공)


 // 현재 좌표에서 4방향을 모두 검사한다
 // 북쪽
 P->Up(); // 임시로 점을 북쪽으로 한칸 옮긴다
 if((P->X()!=T.X())||(P->Y()!=T.Y())) // 스택에 저장된 최근 경로값과 현재 좌표가 같지 않다면 
 {          // 같게 된다면 이 방향으로는 경로가 존재하지 않으므로 skip한다
  if(!IsBlock(P)) // 벽이 아니면
  {
   result = Find(P->X(),P->Y(),x2,y2); // 이 지점부터 다시 경로를 찾는다 ex) (3,2)->(13,13) => (3,2)->(3,1)->(13,13)
   if(result == 0) // 경로가 없으면
    Path->Pop(); // 지나간 경로를 지운다
   else
    return result; // 경로가 존재한다면 1을 반환하고 종료
  }
 }
 P->Down(); // 점을 다시 제자리로

 // 남쪽 (알고리즘은 위와 동일)
 P->Down();
 if((P->X()!=T.X())||(P->Y()!=T.Y()))
 {
  if(!IsBlock(P))
  {
   result = Find(P->X(),P->Y(),x2,y2);
   if(result == 0)
    Path->Pop();
   else
    return result;
  }
 }
 P->Up();

 // 서쪽
 P->Left();
 if((P->X()!=T.X())||(P->Y()!=T.Y()))
 {
  if(!IsBlock(P))
  {
   result = Find(P->X(),P->Y(),x2,y2);
   if(result == 0)
    Path->Pop();
   else
    return result;
  }
 }
 P->Right();

 // 동쪽
 P->Right();
 if((P->X()!=T.X())||(P->Y()!=T.Y()))
 {
  if(!IsBlock(P))
  {
   result = Find(P->X(),P->Y(),x2,y2);
   if(result == 0)
    Path->Pop();
   else
    return result;
  }
 }
 P->Left();


  return 0; // 4방향 모두 경로가 없으므로 0을 반환
   
}


void Maze::Sol()
{

 if(Path->IsEmpty()) throw "Error"; // 스택이 비어있거나 Find함수가 먼저 실행되지 않았을때

 int i,j;
 
 std::cout << "Maze-\n";
 for(i=0;i<15;i++)
 {
  for(j=0;j<15;j++)
  {
   std::cout << Map[i][j] << " ";
  }
  std::cout << "\n";
 }

 std::cout << "\n" << "Solution-\n";
 
 int sol[15][15];
 Location temp;
 for(i=14;i>=0;i--)
  for(j=14;j>=0;j--)
   sol[i][j]=0;
 while(!Path->IsEmpty())
 {
  temp = Path->Pop();
  sol[temp.Y()][temp.X()] = 1;
 }

 for(i=0;i<15;i++)
 {
  for(j=0;j<15;j++)
  {
   std::cout << sol[i][j] << " ";
  }
  std::cout << "\n";
 }

}