[알고리즘] BFS 너비우선탐색 (Stack으로 구현)미로 찾기

BFS탐색은 보통 Queue로 많이들 구현하는데 Stack으로 한번 구현해보았다.

Queue는 First in First out 구조지만 Stack은 Last in Frist out이다

그래서 스택으로 큐를 구현하려면 스택이 두 개 필요할 것 같다고 생각했다.

물에 담긴 컵을 생각해보았다. 물을 다른 컵에 부어버리면 맨 위에 있는 물이 맨 아래로 내려간다고 생각하면 편하다.

위형태로 스택들이 바뀌면 이지 pop용 Stack영역에서 pop하게 되면 결과적으로 push용 Stack영역의 맨 처음 값을 가져오게 되는 것입니다. 이러면 Queue형태처럼 맨 처음에 넣은 값을 사용하게 되는 것입니다.

 

import java.util.Stack;

public class BfsStack {

	public static void main(String[] args) {
		Stack<Maze> popStack=new Stack<Maze>();//실질적 pop를 위한 스택
		Stack<Maze> pushStack=new Stack<Maze>();//실질적 push를 위한 스택
		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 x=0; //x축
		int y=0; //y축
		
		pushStack.push(new Maze(y,x));// 시작값 스택에넣기
		while(true) {	
			change(popStack,pushStack);// pop스택에 push 스택 옮기기
			y=popStack.peek().y;//스택 top에 있는 y축값 확인
			x=popStack.peek().x;//스택 top에 있는 x축값 확인
			popStack.pop();//스택 맨위값 pop
			change(pushStack,popStack);// push스택에 pop스택 옮기기
			load[y][x]=1;//지나간길 1
			if(y==2&&x==1) {//경로끝값 목적지 좌표값
				System.out.println("경로탐색끝");
				break;
			}else {
				if((y-1)>=0) {//(상) 지도끝이면 못가게 하기위해
					if(load[y-1][x]==0) {// 갈 수 있는 길인지 벽인지 확인
						pushStack.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) {// 갈 수 있는 길인지 벽인지 확인
						pushStack.push(new Maze(y,x+1));
						load[y][x+1]=2;//스택에 푸쉬한 값 2로 표시
					}
				}
				if((y+1)<=load.length-1) {//하 지도끝이면 못가게 하기위해
					if(load[y+1][x]==0) {// 갈 수 있는 길인지 벽인지 확인
						pushStack.push(new Maze(y+1,x));
						load[y+1][x]=2;//스택에 푸쉬한 값 2로 표시
					}					
				}
				if((x-1)>=0) { //좌 지도끝이면 못가게 하기위해
					if(load[y][x-1]==0) {// 갈 수 있는 길인지 벽인지 확인
						pushStack.push(new Maze(y,x-1));
						load[y][x-1]=2;
					}					
				}
			}
			if(pushStack.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 == 2 && j == 1) {//목적지
						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 void change(Stack<Maze> popS,Stack<Maze> pushS) {//위치교환
		while(!pushS.isEmpty()) {
			popS.push(pushS.pop());
		}
	}
}