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.

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

DFS 풀이 방법의 특징

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

자료구조 : -

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

알고리즘을 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;
	}

}