Part2. 8-6 미로 찾기

Chapter8/8-06 · master · easyspubjava / javacoursework · GitLab

Chapter8/8-06 · master · easyspubjava / javacoursework · GitLab

 

 

 

밑에 코드에서는 스택을 이용하여 이전에 방문했던 위치를 저장했고
출구가 존재하면 출구로 나오고 , 존재하지 않으면 쭉 되돌아와서 입구로 나온다고 한다
시작 지점은 0으로 벽을 1로 설정한다

Move 는 움직이는 좌표를 뜻하고

동서남북 돌려가면서 새로운 좌표를 구하고 그 좌표가 방문하지 않은 곳이면
그 좌표를 가진 새로운 객체를 생성해준다.
그리고 동서남북 중에 어디까지 봤는지에 대한 정보(direction)도 같이 저장해둔다.

배열은 행렬 개념이다 보니 y가 먼저 나온다 ( ex.  array[y][x] )

특정 좌표에서 더 이상 갈 direction이 없으면 그때 Stack에서 좌표를 꺼내서 다른 길을 찾아보고
그러다가 출구가 없으면 시작 지점으로 돌아온다.

 

 

미로 정의

public class Maze {

	public int[][] myMaze ={                 // int [][]  멤버 변수
			{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, 1, 1, 1, 0, 1, 1, 1},
			{1, 0, 1, 1, 0, 0, 0, 0},
			{0, 1, 1, 0, 1, 1, 1, 0}
	};
}

 

 

움직이는 좌표 Move

public class Move {

	int direction=0;
	
	public int x=0;
	public int y=0;
	
	public Move(int x,int y){
		this.x = x;
		this.y = y;
	}
}

 

 

움직임을 표시할 변수들 (Robot.java)

    public static int NUMDIRECTIONS =  4;
	public static int WIDTH = 8;
	public static int HEIGHT = 8;
	
	Stack<Move> stack = new Stack<Move>();
	Move Move;
	Maze maze = new Maze();                   // maze 인스턴스 생성
	
	public int[][] DIRECTION_OFFSETS = 
	{
		{0, -1},		// 위쪽으로 이동.
		{1, 0},			// 오른쪽으로 이동.
		{0, 1},			// 아래쪽으로 이동.
		{-1, 0}			// 왼쪽으로 이동.
	};
	
	public static int NOTVISIT = 0;        // NOTVISIT : 방문하지 않은 것을 0으로 설정
	public static int WALL = 1;             // 벽을 정수 1로 설정
	public static int VISIT = 2;
	int[][] markArray = new int[8][8];

 

 

출구를 찾는 부분 (Robot.java)

public void findPath( int startX, int startY, int endX, int endY) {
		
		boolean isEmpty = false; 
		boolean isFound = false;
		int i = 0;

		Move start = new Move(startX, startY);

		start.direction = 0;
		stack.push(start);
		
		while(isEmpty == false && isFound == false) {  // 스택이 비어있지 않고 + 출구를 못 찾았을 때 while문 수행
			
				Move curPos = stack.pop();
				int x = curPos.x;
				int y = curPos.y;
				int direction = curPos.direction;

				while(isFound == false && direction < NUMDIRECTIONS) {  // direction < NUMDIRECTIONS 이 조건으로 동서남북 다 봤는지 체크
				
					int newX = x + DIRECTION_OFFSETS[direction][0];
					int newY = y + DIRECTION_OFFSETS[direction][1];

					if (newX >= 0 && newX < WIDTH
								&& newY >= 0 && newY < HEIGHT
								&& maze.myMaze[newY][newX] == NOTVISIT
								&& markArray[newY][newX] == NOTVISIT) {										
						Move newPosition = new Move(newX, newY);
						newPosition.direction = direction + 1;
						stack.push(newPosition);
						markArray[y][x] = VISIT;

						x = newX;
						y = newY;
						direction = 0;

						if (newX == endX && newY == endY) {
							isFound = true;               // 출구를 찾으면 스택에 길이 저장되어 있는 채로 모든 while문을 빠져나간다.
							newPosition.x = newX;
							newPosition.y = newY;
							newPosition.direction = 0;    // 여기까지 newPosition 초기화 작업
							stack.push(newPosition);
							markArray[newY][newX] = VISIT;  // 방문 처리
						}
					}
                    
					else direction++;
                    
				}  // 내부 while 끝
                
			isEmpty = stack.isEmpty();
            
		}  // 외부 while 끝
	}

 

 

찾은 값  출력하기

public void showPath() {
		int[][] resultArray = new int[8][8];
		boolean isEmpty = false;
		
		
		for(int i = 0; i < HEIGHT; i++) {
			for(int j = 0; j < WIDTH; j++) {
				resultArray[i][j] = maze.myMaze[i][j];
			}
		}
		
		
		for(int i = 0; i < HEIGHT; i++) {
			for(int j = 0; j < WIDTH; j++) {
				if (maze.myMaze[i][j] == WALL) {
					System.out.print("*");
				}
				else if (markArray[i][j] == VISIT) {
					System.out.print("|");
				}
				else {
					System.out.print(" ");
				}
			}
			System.out.print("\n");
		}
		
		
		
		int i = 0;
		while(isEmpty == false) {
			Move move = stack.pop();
			int x = move.x;
			int y = move.y;
			resultArray[y][x] = VISIT;   // 이건 활용 안 한 코드

			if (i > 0) {
				System.out.print("<-");
			}
			System.out.print("(" + x +"," + y + ") ");
			i++;
			isEmpty = stack.isEmpty();
		}
		System.out.println();
	}