> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/graph-dfs-bfs/maze_bfs.md).

# Maze\_BFS

There is a **ball** in a maze with empty spaces and walls. The ball can go through empty spaces by rolling **up**, **down**, **left** or **right**, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the ball's **start position**, the **destination** and the **maze**, determine whether the ball could stop at the destination.

The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.

![](/files/-MREKHTWGga1uginpCSW)

![](/files/-MREKO7_-7gHKehR9whm)

**문제 접근 방법**

![](/files/-MREIwEzadGZ6-XrCMLt)

**자료구조** : Queue

**알고리즘** : Queue template + KEEP ROLLING PROCESS\
1\. 기본적으로 Queue Template을 적용한다.\
2\. 문제에서 주어진 조건인 벽을 만나기 전까지 Keep Rolling process를 구현한다.\
   Maze 유효한 범위내에서 계속 그 방향으로 직진한다.

```java
while(nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] != 1) {//조건이 참일 동안 KEEP ROLLING! 이 문제의 핵심!
   nx += dir[0];
   ny += dir[1];
}
```

**이 문제의 핵심**\
다른 그래프 문제들과 달리 이 문제에서는 탐색할 다음 노드를 정할 때 바로 옆의 왼쪽 노드 또는 바로 옆의 오른쪽 노드가 아니라 벽('1')을 만날 때까지 그 방향으로 쭉 진행해서 벽('1')을 만나기 직전의 위치가 그 다음 노드가 된다는 것이다. 이 특수한 process를 구현해서 다음 노드를 결정하고, 계속 traverse한다.&#x20;

**DFS 풀이법과 BFS 풀이법 비교**\
1\. DFS : DFS는 깊이 있게 쭉 파고든다. 재귀호출 또는 스택으로 구현 가능하다.\
2\. BFS : BFS는 level별로 탐색을 진행한다.

**알고리즘을 Java로 구현**

```java
package graph;
import java.util.*;
public class Maze_BFS {
	//이 문제의 핵심은 무엇인가.
	//DFS 풀이법과 BFS 풀이법의 비교, 차이점.
	public static void main(String[] args) {
		int[][] maze ={
				  {0,0,1,0,0},
				  {0,0,0,0,0},
				  {0,0,0,1,0},
				  {1,1,0,1,1},
				  {0,0,0,0,0}
				};
		int[] start = {0,4};
		int[] dest = {4,4};
		int[] dest2 = {3,2};
		Maze_BFS a = new Maze_BFS();
		System.out.println(a.hasPath(maze,start,dest));
		
		System.out.println("Start(0,4) and Destination(4,4) : "+a.hasPath(maze,start,dest));
		System.out.println("Start(0,4) and Destination(3,2) : "+a.hasPath(maze,start,dest2));
	}
	int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};//상 하 좌 우 
	int m,n;
	public boolean hasPath(int[][] maze, int[] start, int[] dest) {//hasPath 없어도 될 것 같은데 뭔가 visited 가 걸린다.
		//에러 제외 
		if(maze == null || maze.length == 0) return false;
		//0.담을 그릇 생성 
		m = maze.length;
		n = maze[0].length;
		boolean[][] visited = new boolean[m][n];//중복을 체크하는 배열. set으로 하거나 원래 좌표를 distintive한 다른 숫자값으로 처리하면 추가 저장공간 불필요.
		System.out.println("===================================");
		return bfs(maze,start,dest,visited);
	}
	public boolean bfs(int[][] maze, int[] start, int[] dest, boolean[][] visited) {
		//아닌 경우를 조건으로하여 예외처리.
		if(start[0] < 0 || start[0] >= m || start[1] < 0 || start[1] >= n || visited[start[0]][start[1]])
			return false;
		
		//1.담을 그릇 생성 
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(start);
		visited[start[0]][start[1]] = true;
		
		//탐색을 시작한다. (queue recursive loop)
		while(!queue.isEmpty()) {
			//큐에서 노드하나 뽑는다.
			int curr[] = queue.poll();
			//사방으로 돌린다.
			for(int[] dir:dirs) {
				int nx = curr[0];//queue에서 꺼낸 좌표는 for문 안에 들어와야한다. 
				int ny = curr[1];
				if(nx == dest[0] && ny == dest[1]) return true;//queue에서 나온 것이 목적지인지 확인!(처음엔 그럴리 없지만!)
				while(nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] != 1) {//조건이 참일 동안 KEEP ROLLING! 이 문제의 핵심!
					nx += dir[0];
					ny += dir[1];
				}
				nx -= dir[0];
				ny -= dir[1];
				if(visited[nx][ny]) continue;//방문했던 노드라면 아래 동작 제외. 
				queue.offer(new int[] {nx,ny});//큐에 새로운 좌표를 넣고 recursively proceed.
				visited[nx][ny] = true;
			}
		}
		return false;
	}
	

}

```