[알고리즘] DFS 깊이우선탐색 미로찾기 (Queue로구현)

미로찾기 지도

스택 구조로 만든 DFS 미로 찾기를 큐 구조로 바꾸어 보았다.

큐를 이용해서 스택처럼 사용하도록 메서드를 만들었다. 그 메서드는 change() 메서드이다.

메서드는 아래 그림과 같다.

change() 메소드 설명

import java.util.LinkedList;
import java.util.Queue;

public class DfsQue {
	public static void main(String[] args) {
		Queue<Maze> que=new LinkedList<Maze>();//실질적 poll를 위한 스택
		//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축
		
		que.offer(new Maze(y,x));// 시작값 스택에넣기
		while(true) {	
			Maze maze=change(que);// poll스택에 offer 스택 옮기기
			y=maze.y;//스택 top에 있는 y축값 확인
			x=maze.x;//스택 top에 있는 x축값 확인
			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) {// 갈 수 있는 길인지 벽인지 확인
						que.offer(new Maze(y-1,x));
						load[y-1][x]=2;//스택에 푸쉬한 값 2로 표시
					}
				}
				if((x+1)<=load[y].length-1) {//우 지도끝이면 못가게 하기위해
					if(load[y][x+1]==0) {// 갈 수 있는 길인지 벽인지 확인
						que.offer(new Maze(y,x+1));
						load[y][x+1]=2;//스택에 푸쉬한 값 2로 표시
					}
				}
				if((y+1)<=load.length-1) {//하 지도끝이면 못가게 하기위해
					if(load[y+1][x]==0) {// 갈 수 있는 길인지 벽인지 확인
						que.offer(new Maze(y+1,x));
						load[y+1][x]=2;//스택에 푸쉬한 값 2로 표시
					}					
				}
				if((x-1)>=0) { //좌 지도끝이면 못가게 하기위해
					if(load[y][x-1]==0) {// 갈 수 있는 길인지 벽인지 확인
						que.offer(new Maze(y,x-1));
						load[y][x-1]=2;
					}					
				}
			}
			if(que.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 static Maze change(Queue<Maze> que) {
		int lastIndex=que.size()-1;//마지막 값 가져오기 위해
		for(int i=0;i<=lastIndex;i++) {//마지막 값까지 반복
			if(i==lastIndex) {//만약 마지막값이면 
				return que.poll() ; //안에 값 반환
			}
			que.offer(que.poll());//뺴낸값을 다시 맨뒤로 넣기
		}
		return null;
	}
}

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;
	}	
}