> 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_dfs.md).

# Maze\_DFS

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/-MR5A8Ca7KjiuT5V5sFe)

![](/files/-MR5ALFgW0zgaFpBTaYh)

**이 문제의 중요한 특징이자 핵심은, 벽('1')을 만나기 전까지 쭉 진행하는 것이다!**

**DFS 풀이 방법의 특징**

함수 호출 시 한번 호출하면 깊이 있게 끝까지 파고든다.

자료구조 : -

**알고리즘**\
1\. start(x,y)에서 상/하/좌/우로 탐색한다.\
2\. 상/하/좌/우 방향으로 범위가 유효한 범위동안 쭉 그 방향으로 계속 진행한다.\
     x += dir\[0], y += dir\[1]

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

```java
package graph;

public class Maze_DFS_practice {

	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_DFS_practice a = new Maze_DFS_practice();
		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 m,n;
	int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
	public boolean hasPath(int[][] maze, int[] start, int[] dest) {
		//예외 제외
		if(maze == null || maze.length == 0) return false;
		
		m = maze.length;
		n = maze[0].length;
		
		//그릇 생성 
		boolean[][] visited = new boolean[m][n];//중복 방지를 위해 maze크기의 boolen 배열을 생성한다. ex ) {0,1} = true, {2,4} = true 를 저장.
		return dfs(maze,start,dest,visited);
	}
	public boolean dfs(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;
		
		//maze 유효 범위내에 속한다면
		visited[start[0]][start[1]] = true;
		if(start[0] == dest[0] && start[1] == start[1])
			return true;
		
		//4방으로 탐색. 
		for(int[] dir:dirs) {
			int x = start[0];
			int y = start[1];
			//THE CORE PART OF THIS PROBLEM. KEEP ROLLING TILL HIT BY WALL('1')
			while(x>=0 && x<m && y>=0 && y<n && maze[x][y] != 1) {
				x += dir[0];
				y += dir[1];
			}
			x -= dir[0];
			y -= dir[1];
			
			if(dfs(maze,new int[] {x,y}, dest, visited)) {
				return true;
			}
		}
		return false;
	}

}

```