Hello! In this course, we will provide an in-depth explanation of an algorithm problem using JavaScript, specifically “Maze Exploration.” This is one of the frequently appearing problem types in coding tests, where the goal is to find a path from the starting point to the destination in a given maze. This problem can be solved using graph search algorithms such as BFS (Breadth-First Search) or DFS (Depth-First Search).
Problem Description
Problem: Check if there is a path from the starting point (start) to the destination (end) in a given 2D array representing a maze. The path in the maze can follow ‘0’ (a traversable space), while ‘1’ (an obstacle) cannot be passed.
For example, let’s assume the maze is as follows:
[
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0]
]
The starting point is (0, 0) and the destination is (4, 4). In other words, we need to determine whether there exists a path from (0, 0) to (4, 4) while exploring the maze.
Input and Output
- Input: 2D array (maze), starting point (start), destination (end)
- Output: Whether a path exists (true/false)
Approach to Problem Solving
To solve this problem, we can use BFS (Breadth-First Search) or DFS (Depth-First Search) algorithms. BFS is suitable for finding the shortest path, but since we only need to check for the existence of a path in this problem, we can also solve it using DFS.
Algorithm Explanation
1. **Basic Setup**: The following process is needed to explore the maze.
- Add all nodes to be explored to the stack (for DFS).
- Mark explored nodes as visited to prevent duplicate exploration.
- Move in all possible directions (up, down, left, right) from the current position.
- If the target position is reached, return true.
- If all paths have been explored and the target is not reached, return false.
JavaScript Implementation
Now, let’s implement the above algorithm in JavaScript. Below is the specific code for the DFS algorithm for maze exploration:
function isPathExist(maze, start, end) {
const rows = maze.length;
const cols = maze[0].length;
// Movement direction array (up, down, left, right)
const directions = [
[-1, 0], // up
[1, 0], // down
[0, -1], // left
[0, 1] // right
];
// Initialize stack and visited array
const stack = [start];
const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
visited[start[0]][start[1]] = true;
// DFS exploration
while (stack.length > 0) {
const [x, y] = stack.pop();
// If the destination is reached
if (x === end[0] && y === end[1]) {
return true;
}
// Move in each direction
for (const [dx, dy] of directions) {
const newX = x + dx;
const newY = y + dy;
// Check range and visit status
if (newX >= 0 && newX < rows && newY >= 0 && newY < cols &&
maze[newX][newY] === 0 && !visited[newX][newY]) {
visited[newX][newY] = true;
stack.push([newX, newY]);
}
}
}
// If unreachable
return false;
}
// Test
const maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0]
];
console.log(isPathExist(maze, [0, 0], [4, 4])); // true
Code Explanation
The above code implements the process of finding a path from the starting point to the destination in a given maze using DFS (Depth-First Search). The main steps are as follows:
- Initial Setup: First, initialize the number of rows and columns in the maze and set the movement directions in an array. The directions we can move are up, down, left, and right.
- Initialize Stack and Visited Array: Use a stack to explore paths for DFS, marking visited positions as 'true'.
- DFS Iteration: Pop a position from the stack to get the current position and check if it is the destination. If the destination is reached, return true.
- Check Move Possibility: Check all directions to confirm if the new position is within range, has no obstacles, and hasn’t been visited before adding it to the stack.
Performance Analysis
The time complexity of this algorithm is O(V+E), where V is the number of vertices (i.e., all positions in the maze) and E is the number of edges (i.e., the number of possible movements from each position). In the worst case, we need to explore all positions, which is why this complexity is necessary. The space complexity is O(V) as space is required for the visited array.
Conclusion
In this lecture, we discussed how to solve the maze exploration problem using JavaScript. We learned basic code and techniques to check the existence of a path through the maze using the DFS algorithm. These types of problems frequently appear in coding tests, so practice various modified problems to build your confidence.
In the next lecture, we will cover more complex maze exploration problems or other types of algorithm problems, so please look forward to it!