[Java 실습] BFS(너비 우선 탐색) 미로 탐색(큐)

map : 길 = 0, 갈수 없는 길(벽) = 1

 

visited 배열을 통해 들렸던 길은 다시 들리지 않는다. (boolean으로 판단)

 

현재 인덱스를 저장하는 Index 클래스를 매개변수로 받아

Way() 메서드를 통해 상하좌우를 검색하고 그 값을 offer한다.

 

offer한 인덱스를 poll하고, 위치를 변경한다.

언제까지? 탈출 (4,4) 할때까지.

---

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

public class BfsQueue {
	 // 인덱스를 저장해주는 큐
	 static Queue<Index> qQueue = new LinkedList<>();
	 // 들린 곳을 체크해줌
	 static boolean [][] visited = new boolean[5][5];
	 // 길=0, 벽=1
	 static int[][] map = {
			 {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}};

	 public static void main(String[] args) {
		 dfs(0,0);
	  }
	 // 시작 행, 열
	 public static void dfs(int x, int y) {
		 Index hi = new Index(x,y);
		 // 방문 처리
		 visited[x][y] = true;
		 
		 while(true) {
			 // x=4, y=4
			 if(hi.getX() == 4 && hi.getY() == 4) {
				 System.out.println("탈출했습니다!");
				 break;
			 } else {
				 // 검색 과정
				 way(hi);
				 // 현재 위치를 poll
				 Index temp = qQueue.poll();
				 hi.setX(temp.getX());
				 hi.setY(temp.getY());
				 // 현재 위치를 변경
				 System.out.println(""+hi.getX() +" "+ hi.getY());
				 // 방문했다고 변경
				 visited[hi.getX()][hi.getY()] = true;
			 }
		  }
	  } 
	  public static void way(Index hi) {

		 // 위로 이동
		  if(hi.getX()>0) { 
			  if(map[hi.getX()-1][hi.getY()] != 1 && !(visited[hi.getX()-1][hi.getY()])) {
				  qQueue.offer(new Index(hi.getX()-1, hi.getY()));
			  }
		 }
		 // 왼쪽으로 이동
		 if(hi.getY()>0) {
			 if(map[hi.getX()][hi.getY()-1] != 1 && !(visited[hi.getX()][hi.getY()-1])) {
				 qQueue.offer(new Index(hi.getX(), hi.getY()-1));
			 }
		 }
		 // 오른쪽으로 이동
		 if(hi.getY()<4) {
			 if(map[hi.getX()][hi.getY()+1] != 1 && !(visited[hi.getX()][hi.getY()+1])) {
				 qQueue.offer(new Index(hi.getX() , hi.getY()+1));
			 }
		 }
		 // 아래로 이동
		 if(hi.getX()<4) { 
			 if(map[hi.getX()+1][hi.getY()] != 1 && !(visited[hi.getX()+1][hi.getY()])) {
				 qQueue.offer(new Index(hi.getX()+1, hi.getY()));
			 }
		 }
	 }
}

---

느낀점

 

스택을 구현해 놨더니 Queue로 바꾸는건 크게 어렵지 않았다.

물론 스택과 다른 면이 있기 때문에 공부하는 과정이 있었기에 어려움을 덜 느낀듯 하다.