[알고리즘] DFS 깊이 우선 탐색 (Stack 사용)미로

미로 지도

팀원들과 알고리즘을 확실히 만든 후 짜보았다.

나는 좌하 우상 순으로 하려고 처음에 짰는데 완전히 반대로 나와서 당황했는데 스택을 사용하는 거니 순서를 반대로 해서 코드로 짜는 게 맞다는 걸 이번 기회에 배웠다. 스택은 LastInLastOut구조니 깐..

시작점은 0,0 이랑 끝점은 15,15로 설정해 두었다

import java.util.Arrays;
import java.util.Stack;

public class DfsAl {

	public static void main(String[] args) {
		Stack<Maze> stack=new Stack<Maze>();
		//int[][] load = {{0,0,0,0,0},{0,-1,-1,-1,0},{0,0,0,-1,0},{0,-1,0,-1,0},{0,-1,0,0,0}};
		int[][] load = { {0,0,0,0,0,-1,-1,0,0,0,0,0,0,-1,0,0}, {0,-1,-1,-1,0,-1,-1,0,-1,-1,-1,-1,0,0,0,-1,},
	            {0,-1,-1,-1,0,0,0,0,0,0,-1,-1,-1,-1,0,-1},{0,-1,0,0,0,-1,-1,0,-1,0,-1,-1,-1,-1,0,-1},
	            {0,-1,0,-1,-1,-1,-1,0,-1,0,-1,-1,-1,-1,0,-1},{0,-1,0,-1,0,0,0,0,-1,0,0,0,0,0,0,0},
	            {0,-1,0,-1,0,-1,-1,0,-1,0,-1,-1,0,-1,-1,0},{0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,-1,-1,0},
	            {0,0,0,-1,0,0,0,0,0,0,0,0,0,-1,-1,0},{0,-1,0,-1,0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
	            {0,-1,0,-1,0,0,0,-1,0,0,0,0,0,0,0,0},{0,-1,0,0,0,-1,-1,-1,-1,-1,0,-1,-1,-1,-1,0},
	            {0,-1,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,0,0},{-1,-1,0,-1,-1,-1,-1,0,-1,-1,0,0,-1,0,-1,0},
	            {0,0,0,0,0,0,0,0,-1,-1,-1,0,-1,0,-1,-1},{0,-1,-1,-1,-1,-1,-1,0,-1,-1,-1,0,0,0,0,0}
	      };
		int x=0; //x축
		int y=0; //y축
		
		stack.push(new Maze(y,x));// 시작값 스택에넣기
		while(true) {			
			y=stack.peek().y;//스택 top에 있는 y축값 확인
			x=stack.peek().x;//스택 top에 있는 x축값 확인
			stack.pop();//스택 맨위값 pop
			load[y][x]=1;//지나간길 1
			if(y==15&&x==15) {//경로끝값 목적지 좌표값
				System.out.println("경로탐색끝");
				break;
			}else {
				if((y-1)>=0) {//(상) 지도끝이면 못가게 하기위해
					if(load[y-1][x]==0) {// 갈 수 있는 길인지 벽인지 확인
						stack.push(new Maze(y-1,x));
						load[y-1][x]=2;//스택에 푸쉬한 값 2로 표시
					}
				}
				if((x+1)<=load[y].length-1) {//우 지도끝이면 못가게 하기위해
					if(load[y][x+1]==0) {// 갈 수 있는 길인지 벽인지 확인
						stack.push(new Maze(y,x+1));
						load[y][x+1]=2;//스택에 푸쉬한 값 2로 표시
					}
				}
				if((y+1)<=load.length-1) {//하 지도끝이면 못가게 하기위해
					if(load[y+1][x]==0) {// 갈 수 있는 길인지 벽인지 확인
						stack.push(new Maze(y+1,x));
						load[y+1][x]=2;//스택에 푸쉬한 값 2로 표시
					}					
				}
				if((x-1)>=0) { //좌 지도끝이면 못가게 하기위해
					if(load[y][x-1]==0) {// 갈 수 있는 길인지 벽인지 확인
						stack.push(new Maze(y,x-1));
						load[y][x-1]=2;//스택에 푸쉬한 값 2로 표시
					}					
				}
			}
			if(stack.isEmpty()) {
				break;
			}			
		}	
		for (int i = 0; i < load.length; i++) {	//수행한 길을 보여주기
			for (int j = 0; j < load[i].length; j++) {
				if (load[i][j] == 0) {
					System.out.print("□");	//아직 안간길
				} else if (load[i][j] == 1) {
					if (i == 15 && j == 15) {//목적지
						System.out.print("X");	//종료위치
					} else {
						System.out.print("@");	//간길
					}
				} else if (load[i][j] == -1) {
					System.out.print("■");	//벽
				}else if(load[i][j] == 2) {
					System.out.print("%");//스택에서 탐색하고 남은 길
				}
			}
			System.out.println();
		}
	}
}

public class Maze {
	int x;
	int y;	
	Maze(int y,int x){
		this.y=y;
		this.x=x;
	}	
	@Override
	public String toString() {
		return y+""+x;
	}	
}

출력결과