JavaScript Coding Test Course, Depth First Search

Problem: Maze Exploration

This is a problem to determine whether there is a path from the starting point to the destination in the given 2D array. The values of the array are given as 0 (passable) and 1 (impassable). The starting point is (0, 0) and the destination is (N-1, M-1). Movement is allowed only up, down, left, and right, and if a path exists, it should return true; if not, it should return false.

Example Problem

Input

    [
        [0, 0, 1, 0],
        [1, 0, 1, 0],
        [0, 0, 0, 0],
        [0, 1, 1, 0]
    ]

Output

true

Explanation

In the above example, starting from the starting point (0, 0), the path goes through (1, 1), (2, 1), (2, 2), (2, 3), (3, 3) to reach the destination (3, 3).

Problem Solving Process

1. Overview of the Algorithm

This problem can be solved using the Depth First Search (DFS) algorithm. DFS is a method that goes as deep as possible into the nodes before backtracking to explore other paths. We will implement this using recursion. DFS is applied to explore the maze and check whether it is possible to reach the destination from the starting point.

2. Implementing the DFS Algorithm

To implement DFS, the following steps are necessary:

  1. Check if the current position is within bounds.
  2. Check if the current position is an impassable point.
  3. Check if the current position is the destination.
  4. Mark the current position as visited.
  5. Recursively call DFS in all four directions (up, down, left, right).
  6. After exploring all paths, unmark the visited position.

3. Code Implementation

The following code implements the DFS algorithm using JavaScript:


function isPathExists(maze) {
    const rows = maze.length;
    const cols = maze[0].length;

    function dfs(x, y) {
        // Boundary conditions
        if (x < 0 || y < 0 || x >= rows || y >= cols) return false;
        // Impassable point
        if (maze[x][y] === 1) return false;
        // Destination
        if (x === rows - 1 && y === cols - 1) return true;

        // Mark current position as visited
        maze[x][y] = 1;

        // Explore DFS in four directions
        const found = dfs(x + 1, y) || dfs(x - 1, y) || dfs(x, y + 1) || dfs(x, y - 1);

        // Unmark visited position
        maze[x][y] = 0;

        return found;
    }

    return dfs(0, 0);
}

// Example Test
const maze = [
    [0, 0, 1, 0],
    [1, 0, 1, 0],
    [0, 0, 0, 0],
    [0, 1, 1, 0]
];

console.log(isPathExists(maze)); // Output: true

4. Code Explanation

Let me explain the key parts of the code:

  • Boundary condition check: Ensures the current position does not exceed the array boundaries.
  • Impassable point check: Verifies if the value at the current position is 1 to determine if it is passable.
  • Destination reached: Returns true if the current position is the destination (N-1, M-1).
  • Mark as visited: Marks the current position to prevent duplicate exploration.
  • Recursive call: Calls DFS recursively in the four directions to explore the path.
  • Unmarking: Unmarks the visited position after the exploration is complete.

5. Time Complexity Analysis

The time complexity of this algorithm is O(N * M), where N is the number of rows and M is the number of columns. This is because each cell can be visited once. However, there may be additional memory required in the worst-case scenario due to stack space overhead from recursion.

Conclusion

In this tutorial, we learned how to solve the maze exploration problem using Depth First Search (DFS). DFS can be effectively used even in complex graph structures, and it can be applied to various problems. Once you understand the characteristics and workings of DFS, it is advisable to apply it to different problems. In the next tutorial, we will explore the Breadth First Search (BFS) algorithm. I hope you found this tutorial helpful.