미로 찾기!

*Git : https://github.com/bsh6463/Maze

bsh6463/Maze

입구부터 출구까지 길을 찾자!

 

미로찾기는 stack으로 활용이 가능하다. 왜냐? 갈림길에서 한쪽 방향을 선택하고 쭉! 들어갔을 때(DFS) 

 

길이 없다면 다시 갈림길로 돌아와서 다른 길로 가야한다. 

 

즉, DFS의 개념이 사용된다. 

 

다시말해, 길을 찾아갈 때 현재 노드와 인접한 노드들을 stack에 추가하고 

 

stack 가장 맨위의 노드로 진행 했을 때, 더 이상 갈 노드가 없다면 stack에 있는 다음 노드를 꺼내서 가면 

 

갈림길에서 다른 길로 가는 것과 동일한 효과이다.

 x에서 인접1 방향으로 갔더니 길이 없음... 인접2 방향으로 가자.

stack으로 구현한 경우, pop()해서 인접1로 갔는데, 길이 없어서 다시 pop()하여 인접2로 가는 경우

1. 미로를 2차원 배열로 구현하기

---

  아래 그림과 같은 미로를 만들었다.  회색은 벽이고 흰색은 길이다.

2차원 배열을 활용하면 각 칸 마다 index를 지정하여 벽인지, 길인지 값을 입력할 수 있다.

즉 앞으로 0만 따라서 탈출해 보도록 하겠다.

 

코드로는 아래와 같이 직접 입력해줬다.

package graph;

public class Maze {

    public int[][] myMaze = {
            {0,1,1,1,0,1,1,1},
            {0,0,0,1,0,0,0,0},
            {1,1,0,0,0,1,0,1},
            {1,1,0,1,1,1,0,1},
            {1,0,0,1,0,0,0,0},
            {0,0,1,1,0,1,1,1},
            {1,0,1,1,0,0,0,0},
            {1,1,1,0,0,1,1,0}
    };

    public int[][] getMyMaze() {
        return myMaze;
    }
}

 

2. 이동 가능한 인접 노드 확인하는 방법

---

미로에서 각 지점(index)에 Point 객체가 있다고 해보자. 

 

DSF는 인접 노드(객체)를 따라 depth방향으로 탐색해 가는 방법이다.

 

즉 인접한 point 객체를 찾아야 한다.

 

인접한 point 객체를 찾기 위해, 현재 위치에서 상/하/좌/우 방향으로 1칸 씩 이동하며

이동이 가능한 인접 노드인지 아래 조건들을 통해 확인한다.

 

- 탐색할 노드가 index 범위 내에 있는지

- 아직 방문하지 않은 노드인지

- 길인지 벽인지 

 

3. Point class

---

따라서 point class를 만들자.

 

인접 노드 탐색이 가능하도록, 상/하/좌/우로 이동시키는 move method를 추가했다.

 

생성자는 종류별로 만들어 놨다. 

package graph;

public class Point {

    private int row;
    private int col;

    public Point(int row, int col){
        this.row = row;
        this.col = col;
    }

    public Point(Point point){
        this.row = point.getRow();
        this.col = point.getCol();
    }

    public Point(){
    }

    public int getRow() {
        return row;
    }

    public void setRow(int row) {
        this.row = row;
    }

    public int getCol() {
        return col;
    }

    public void setCol(int col) {
        this.col = col;
    }


    public void move(int n){
        if(n == 1){
            this.col--;
            System.out.println("좌 탐색");
        }
        else if(n == 2){
            this.col++;
            System.out.println("우 탐색");
        }
        else if(n==3){
            this.row--;
            System.out.println("상 탐색");
        }
        else if(n==4){
            this.row++;
            System.out.println("하 탐색");
        }
    }

}

 

4. pathFinder class

---

 - Stack 을 활용해서 이동할 인접 노드 관리 : Stack<Point> stack

 - 방문한 node를 기록하기 위해 : String[] visitString

 - 각 노드에 대한 방문여부 기록 : boolean[][] visited --> 인스턴스 생성 시 모든 값 false로 초기화

 - 미로 배열 :  public int[][] maze --> 나중에 main에서 입력받음.

 - 아래와 같은 순서로 미로를 찾아갈 것임.

 

- 주의사항! 

    Point temp 사용시 주의해야 함!

      

    왜냐? current에 대한 정보를 temp에 담을 때 주의해야 한다. 

   

    만약 temp에 current 정보를 담고싶어서 temp = current를 한다면! 

   

    temp와 current의 hash가  달랐어도, temp = current를 통해 둘의 hash가 같은 값이 된다. 

 

    즉, 논리 순서상 temp에 current정보를 담고, temp를 stack을 하게되는데 

   

     temp = current 이후에 아무런 초기화 없이 진행한다면?

 

     temp = current = stack.pop() 가 된다. 

 

    따라서 temp와 current의 연결 고리를 끊어버리기 위해 temp를 stack에 올린 후 초기화 시켜버린다.

 

 

- 기타 이동한 경로를 보기위한 method 추가를 했고,

   시작 노드 입력받을 시 벽에 해당하는 노드거나, 범위를 벗어나는 경우 예외를 발생시켰다.
   처리 안하면 냅두면 돌다가 예외발생..

        

5. 코드

---

package graph;

import java.util.LinkedList;
import java.util.Stack;

public class PathFinder {

    Stack<Point> stack;
    boolean[][] visited;
    String[] visitString;
    public int[][] maze;
    int rowNumber;
    int colNumber;
    int count = 0;

    public PathFinder(int rowNumber, int colNumber){

        visited = new boolean[rowNumber][colNumber];
        stack = new Stack<>();
        visitString = new String[50];
        this.rowNumber = rowNumber;
        this.colNumber = colNumber;

    }

    public void findPath(int rowStart, int colStart) throws Exception {

        if(maze[rowStart][colStart] == 1){
            System.out.println("띠용 시작이 불가능 합니다.");
            throw new Exception();
        }
        Point start = new Point(rowStart, colStart);
        stack.push(start);
        Point temp = new Point();

        //방문노드 확인 배열 초기화
        for(int i = 0; i < rowNumber; i++){
            for(int j = 0; j< colNumber; j++){
                visited[i][j] = false;
            }
        }


        //인접 노드 찾기
        Point current = new Point(stack.pop());
        while (true){

            visited[current.getRow()][current.getCol()] = true;
            visitString[count++] = "[" + current.getRow()+"," + current.getCol() + "]";
            System.out.println("현재노드 : [" + current.getRow()+"," + current.getCol() + "]");


            for(int i =1 ; i<5;i++){

                temp.setRow(current.getRow());
                temp.setCol(current.getCol());

                temp.move(i);

                System.out.println("탐색 노드 : [" + temp.getRow()+"," + temp.getCol() + "]");

                if(temp.getRow() >= 0 && temp.getCol() >= 0
                        && temp.getRow() < rowNumber && temp.getCol() < colNumber
                        && visited[temp.getRow()][temp.getCol()] == false
                        && maze[temp.getRow()][temp.getCol()] == 0){
                    System.out.println("해당 노드 이동 가능.");
                    stack.push(temp);
                    //temp의 역할을 여기서 끝! temp 역할이 끝나면 초기화 해주자!
                    temp = new Point();
                }
                else{
                    System.out.println("이동 불가");
                }

                System.out.println("////////////////////////////////////////");

            }

            System.out.println("--------------------------------");

            if(current.getRow() == 7 && current.getCol() == 7) {

                showPath();
                break;
            }

        temp = stack.pop();
        current.setRow(temp.getRow());
        current.setCol(temp.getCol());


        }
    }


   public void showPath(){

        Point temp = new Point();
        for(int i=0; i<count; i++){

            System.out.print(visitString[i] + " - ");

        }
       System.out.println("탈출!");

   }

}

6. 실행 결과

---

현재노드 : [0,0]
좌 탐색
탐색 노드 : [0,-1]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [0,1]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [-1,0]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [1,0]
해당 노드 이동 가능.
////////////////////////////////////////
--------------------------------
현재노드 : [1,0]
좌 탐색
탐색 노드 : [1,-1]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [1,1]
해당 노드 이동 가능.
////////////////////////////////////////
상 탐색
탐색 노드 : [0,0]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [2,0]
이동 불가
////////////////////////////////////////
--------------------------------
현재노드 : [1,1]
좌 탐색
탐색 노드 : [1,0]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [1,2]
해당 노드 이동 가능.
////////////////////////////////////////
상 탐색
탐색 노드 : [0,1]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [2,1]
이동 불가
////////////////////////////////////////
--------------------------------
현재노드 : [1,2]
좌 탐색
탐색 노드 : [1,1]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [1,3]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [0,2]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [2,2]
해당 노드 이동 가능.
////////////////////////////////////////
--------------------------------
현재노드 : [2,2]
좌 탐색
탐색 노드 : [2,1]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [2,3]
해당 노드 이동 가능.
////////////////////////////////////////
상 탐색
탐색 노드 : [1,2]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [3,2]
해당 노드 이동 가능.
////////////////////////////////////////
--------------------------------
현재노드 : [3,2]
좌 탐색
탐색 노드 : [3,1]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [3,3]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [2,2]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [4,2]
해당 노드 이동 가능.
////////////////////////////////////////
--------------------------------
현재노드 : [4,2]
좌 탐색
탐색 노드 : [4,1]
해당 노드 이동 가능.
////////////////////////////////////////
우 탐색
탐색 노드 : [4,3]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [3,2]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [5,2]
이동 불가
////////////////////////////////////////
--------------------------------
현재노드 : [4,1]
좌 탐색
탐색 노드 : [4,0]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [4,2]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [3,1]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [5,1]
해당 노드 이동 가능.
////////////////////////////////////////
--------------------------------
현재노드 : [5,1]
좌 탐색
탐색 노드 : [5,0]
해당 노드 이동 가능.
////////////////////////////////////////
우 탐색
탐색 노드 : [5,2]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [4,1]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [6,1]
해당 노드 이동 가능.
////////////////////////////////////////
--------------------------------
현재노드 : [6,1]
좌 탐색
탐색 노드 : [6,0]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [6,2]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [5,1]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [7,1]
이동 불가
////////////////////////////////////////
--------------------------------
현재노드 : [5,0]
좌 탐색
탐색 노드 : [5,-1]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [5,1]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [4,0]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [6,0]
이동 불가
////////////////////////////////////////
--------------------------------
현재노드 : [2,3]
좌 탐색
탐색 노드 : [2,2]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [2,4]
해당 노드 이동 가능.
////////////////////////////////////////
상 탐색
탐색 노드 : [1,3]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [3,3]
이동 불가
////////////////////////////////////////
--------------------------------
현재노드 : [2,4]
좌 탐색
탐색 노드 : [2,3]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [2,5]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [1,4]
해당 노드 이동 가능.
////////////////////////////////////////
하 탐색
탐색 노드 : [3,4]
이동 불가
////////////////////////////////////////
--------------------------------
현재노드 : [1,4]
좌 탐색
탐색 노드 : [1,3]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [1,5]
해당 노드 이동 가능.
////////////////////////////////////////
상 탐색
탐색 노드 : [0,4]
해당 노드 이동 가능.
////////////////////////////////////////
하 탐색
탐색 노드 : [2,4]
이동 불가
////////////////////////////////////////
--------------------------------
현재노드 : [0,4]
좌 탐색
탐색 노드 : [0,3]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [0,5]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [-1,4]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [1,4]
이동 불가
////////////////////////////////////////
--------------------------------
현재노드 : [1,5]
좌 탐색
탐색 노드 : [1,4]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [1,6]
해당 노드 이동 가능.
////////////////////////////////////////
상 탐색
탐색 노드 : [0,5]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [2,5]
이동 불가
////////////////////////////////////////
--------------------------------
현재노드 : [1,6]
좌 탐색
탐색 노드 : [1,5]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [1,7]
해당 노드 이동 가능.
////////////////////////////////////////
상 탐색
탐색 노드 : [0,6]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [2,6]
해당 노드 이동 가능.
////////////////////////////////////////
--------------------------------
현재노드 : [2,6]
좌 탐색
탐색 노드 : [2,5]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [2,7]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [1,6]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [3,6]
해당 노드 이동 가능.
////////////////////////////////////////
--------------------------------
현재노드 : [3,6]
좌 탐색
탐색 노드 : [3,5]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [3,7]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [2,6]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [4,6]
해당 노드 이동 가능.
////////////////////////////////////////
--------------------------------
현재노드 : [4,6]
좌 탐색
탐색 노드 : [4,5]
해당 노드 이동 가능.
////////////////////////////////////////
우 탐색
탐색 노드 : [4,7]
해당 노드 이동 가능.
////////////////////////////////////////
상 탐색
탐색 노드 : [3,6]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [5,6]
이동 불가
////////////////////////////////////////
--------------------------------
현재노드 : [4,7]
좌 탐색
탐색 노드 : [4,6]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [4,8]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [3,7]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [5,7]
이동 불가
////////////////////////////////////////
--------------------------------
현재노드 : [4,5]
좌 탐색
탐색 노드 : [4,4]
해당 노드 이동 가능.
////////////////////////////////////////
우 탐색
탐색 노드 : [4,6]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [3,5]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [5,5]
이동 불가
////////////////////////////////////////
--------------------------------
현재노드 : [4,4]
좌 탐색
탐색 노드 : [4,3]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [4,5]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [3,4]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [5,4]
해당 노드 이동 가능.
////////////////////////////////////////
--------------------------------
현재노드 : [5,4]
좌 탐색
탐색 노드 : [5,3]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [5,5]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [4,4]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [6,4]
해당 노드 이동 가능.
////////////////////////////////////////
--------------------------------
현재노드 : [6,4]
좌 탐색
탐색 노드 : [6,3]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [6,5]
해당 노드 이동 가능.
////////////////////////////////////////
상 탐색
탐색 노드 : [5,4]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [7,4]
해당 노드 이동 가능.
////////////////////////////////////////
--------------------------------
현재노드 : [7,4]
좌 탐색
탐색 노드 : [7,3]
해당 노드 이동 가능.
////////////////////////////////////////
우 탐색
탐색 노드 : [7,5]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [6,4]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [8,4]
이동 불가
////////////////////////////////////////
--------------------------------
현재노드 : [7,3]
좌 탐색
탐색 노드 : [7,2]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [7,4]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [6,3]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [8,3]
이동 불가
////////////////////////////////////////
--------------------------------
현재노드 : [6,5]
좌 탐색
탐색 노드 : [6,4]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [6,6]
해당 노드 이동 가능.
////////////////////////////////////////
상 탐색
탐색 노드 : [5,5]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [7,5]
이동 불가
////////////////////////////////////////
--------------------------------
현재노드 : [6,6]
좌 탐색
탐색 노드 : [6,5]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [6,7]
해당 노드 이동 가능.
////////////////////////////////////////
상 탐색
탐색 노드 : [5,6]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [7,6]
이동 불가
////////////////////////////////////////
--------------------------------
현재노드 : [6,7]
좌 탐색
탐색 노드 : [6,6]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [6,8]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [5,7]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [7,7]
해당 노드 이동 가능.
////////////////////////////////////////
--------------------------------
현재노드 : [7,7]
좌 탐색
탐색 노드 : [7,6]
이동 불가
////////////////////////////////////////
우 탐색
탐색 노드 : [7,8]
이동 불가
////////////////////////////////////////
상 탐색
탐색 노드 : [6,7]
이동 불가
////////////////////////////////////////
하 탐색
탐색 노드 : [8,7]
이동 불가
////////////////////////////////////////
--------------------------------
[0,0] - [1,0] - [1,1] - [1,2] - [2,2] - [3,2] 
- [4,2] - [4,1] - [5,1] - [6,1] - [5,0] - [2,3] 
- [2,4] - [1,4] - [0,4] - [1,5] - [1,6] - [2,6] 
- [3,6] - [4,6] - [4,7] - [4,5] - [4,4] - [5,4] 
- [6,4] - [7,4] - [7,3] - [6,5] - [6,6] - [6,7] 
- [7,7] - 탈출!

실제 이동 경로

방문 노드 확인 결과

 

7. 앞으로 조심해야 할 점..

어떤 한 객체 a를 stack에 push한 경우 a와 stack의 top에 있는 객체의 hash가 같다!

그리고 객체 b와 객체 a가 같다고 하는 경우도 hash가 같아진다. 달랐어도..

혹시 모르니 temp의 용도가 끝난 경우 초기화를 해주자..