# 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;
	}

}

```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://heunnajo.gitbook.io/algorithms-problem-solving-skills/graph-dfs-bfs/maze_dfs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.