[JavaScript] C->JS/JS로 스택 구현 / 미로찾기

1.     서론

 

자바스크립트로 스택을 구현하고, 스택을 이용하여 현재 위치에서 출구까지의 경로를 기록하고 미로를 탈출한다.

 

2. Pseudo Code

 

Int main()

{

          스택과 위치를 기록할 공간을 생성한다.

          스택을 초기화하고 미로를 불러낸다.

          지정된 시작점을 찾고 시작점에서부터 미로를 탈출한다.

          while(탈출구까지)

          {

                    do현재 위치를 좌표에 입력한다;

                      현재 위치를 표시한다.(이미 다녀간 위치)

                    

                    do동쪽에 이동 가능한 길이 있는지 확인한다.

                      서쪽에 이동 가능한 길이 있는지 확인한다.

                      남쪽에 이동 가능한 길이 있는지 확인한다.

                      북쪽에 이동 가능한 길이 있는지 확인한다.

 

                      If(스택이 비었다면)

                      {

                              then탈출 실패

                      }

                      else(이동 가능하다면)

                      {

                              then이동한 위치를 기록하고 출력한다.

                      }

          (탈출구를 발견하였다.)

          }

          도착 위치를 기록하고 탈출한다.

}

 

3. maze.js(Code)

function Stack() {

    
//스택의 요소가 저장되는 배열
    
var dataStore = new Pos;
   
this.dataStore = [];
    
//스택의 위치
    
this.top = -1;
    
//함수정의
    
this.push   = push;
    
this.pop    = pop;

}

//미로 입력과 출력
var maze = new Array(new Array(7), new Array(7), new Array(7), new Array(7), new Array(7), new Array(7), new Array(7));
 var maze = [['0', '0', '0', '0', '0', '0', '0'],
    
 ['0', '1', '1', '1', '0', '1', '0'],
    
 ['0', '0', '0', '1', '0', '1', '0'],
    
 ['s', '1', '0', '1', '1', '1', '0'],
    
 ['0', '1', '1', '1', '1', '1', '0'],
    
 ['0', '1', '1', '0', '1', '1', 'e'],
    
 ['0', '0', '0', '0', '0', '1', '1']];


 console.log("미로찾기를 시작해보자!");

 console.log("미로찾기 출력");

 console.log(maze);


 const MAX_SIZE = 100;

//Position Struct

 function Pos(x,y) {

 this.x = x;
    
 this.y = y;

 }

//초기화 함수
 function Init() 
 {
   
 this.top = -1;

 }

//가득 찼을때

 function Is_full() {
 return(this.top == MAX_SIZE-1);
 }

//비었을 때

 function Is_empty(){
 return(this.top == -1);

 }

//스택에 요소를 추가

 function push(element) {
 if(Is_full())

 {
 
 console.log("Stack is full");
 
 }
 
 else{

 this.top = this.top +1;

 this.dataStore[this.top] = element;

 }
 }

//스택 최상층의 요소를 반환한다.
 function pop() {
 
 //Stack underflow
   
 if(this.top<=-1)
  
 {
  
 console.log("Stack underflow!!!");

 return;
 
 }
 
 else
  
 {
     
 var popped = this.dataStore[this.top];

 //top을 1 감소시킨다.
     
 this.top = this.top -1;
     
 return popped;
 
 }

 }

//동서남북 이동 가능한가 확인 Movable함수
 function Movable(x,y) {
 if(x<0||y<0||x>7||y>7) return;
 if (maze[x][y] != '1' && maze[x][y] != '.') {
 var next = new Pos();
    
 next.x = x;
   
 next.y = y;

  
 stackObj.push(next);
 
 }
 }

 //스택 객체 생성
 var stackObj = new Stack();
 var here = new Pos();

 //시작점 탐색
 for (var i = 0; i < maze.length; i++) {
 for (var j = 0; j < maze[i].length; j++) {

 if (maze[i][j] == 's') {
  
 here.x = i;
      
 here.y = j;
        
 }
  
 }

 }
 console.log("시작점:" + "(" + here.x + "," + here.y + ")");

//시작점에서 출구까지 반복문

 while(maze[here.x][here.y] != 'e') {
 var x = here.x;
   
 var y = here.y;

   
 maze[x][y]='.';

 
 Movable(x + 1, y);
  
 Movable(x - 1, y);
  
 Movable(x, y + 1);
    
 Movable(x, y - 1);

    
 if (Is_empty())
   
 {
     
 console.log("failed");
 // noinspection JSAnnotator
 return ;
   
 }
  
 else {
 
 here = stackObj.pop();
 console.log("(" + here.x + "," + here.y + ")");

 }

 }

 console.log("도착점:"+ "(" + here.x + "," + here.y + ")");
 console.log("탈출 성공!!!!!!!!");

4. 결과

[PE:JavaScript]미로찾기PDF.pdf

0.16MB