[알고리즘] BFS 너비우선탐색 (Queue사용) 미로찾기

미로 모양:

□□□□□
□■■■□
□x□■□
□■□■□
□■□□□

목적지를 x로 잡았다.

Queue를 사용해서 너비 우선 탐색 미로 찾기를 팀원 함께 구상하여 작성해보았다. DFS 스택 버전과 코드가 거의 유사한 거 같다.

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

public class BfsQue {

	public static void main(String[] args) {
		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축
		Queue<Maze> queue=new LinkedList<Maze>();
		queue.offer(new Maze(y,x));// 시작값 큐에넣기
		while(true) {			
			y=queue.peek().y;//큐 top에 있는 y축값 확인
			x=queue.peek().x;//큐 top에 있는 x축값 확인
			queue.poll();//큐 맨위값 poll
			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) {// 갈 수 있는 길인지 벽인지 확인
						queue.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) {// 갈 수 있는 길인지 벽인지 확인
						queue.offer(new Maze(y,x+1));
						load[y][x+1]=2;//큐에 오퍼한 값 2로 표시
					}
				}
				if((y+1)<=load.length-1) {//하 지도끝이면 못가게 하기위해
					if(load[y+1][x]==0) {// 갈 수 있는 길인지 벽인지 확인
						queue.offer(new Maze(y+1,x));
						load[y+1][x]=2;//큐에 오퍼한 값 2로 표시
					}					
				}
				if((x-1)>=0) { //좌 지도끝이면 못가게 하기위해
					if(load[y][x-1]==0) {// 갈 수 있는 길인지 벽인지 확인
						queue.offer(new Maze(y,x-1));
						load[y][x-1]=2;
					}					
				}
			}
			if(queue.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();
		}
	}

}

출력 결과