JavaScript Coding Test Course, Pathfinding

Coding tests are taken by many developers, and they are assessed through various algorithm problems. In this article, we will take a closer look at the algorithm problem-solving process through the ‘pathfinding’ problem. This problem is suitable for using graph traversal techniques such as DFS (Depth-First Search) or BFS (Breadth-First Search).

Problem Description

You need to find a path from the starting point to the destination point in a given 2D grid. Each cell of the grid indicates whether it can be moved to or not, and the following are the problem conditions:

  • The grid has dimensions N x M.
  • Each cell is marked with 0 or 1, where 0 indicates a traversable path and 1 indicates a blocked path.
  • The starting point is at (0, 0) and the destination point is at (N-1, M-1).
  • You can move up, down, left, or right.

Example Input

    4 4
    0 0 1 0
    0 1 0 0
    0 1 1 0
    0 0 0 0

Example Output

    Yes

Problem Solving Process

The algorithm we will use to solve this problem is BFS. BFS is advantageous for finding the shortest path as it explores each node in order. We will solve the problem through the following steps:

1. Create the grid space

Convert the received grid information into an array. This will facilitate access to and movement through each cell.

2. Initialize BFS

Add the starting point (0, 0) to the queue. Additionally, we use an extra array to track visited nodes.

3. Perform BFS search

Repeat the following while the queue is not empty:

  • Dequeue a node to check the current position.
  • Check if the current position is the destination point (N-1, M-1). If so, output ‘Yes’ and terminate the search.
  • For all cells that can be moved to up, down, left, or right, do the following:
    • Check the boundary conditions and whether it has been visited.
    • If the cell’s value is 0 and it has not been visited, add it to the queue and mark it as visited.

If the search completes and the destination point has not been reached, output ‘No’.

4. Code Implementation

    function canReachDestination(grid) {
        const N = grid.length;
        const M = grid[0].length;
        const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        const queue = [[0, 0]];
        const visited = Array.from({length: N}, () => Array(M).fill(false));

        visited[0][0] = true;

        while (queue.length > 0) {
            const [x, y] = queue.shift();

            // Check the destination point
            if (x === N - 1 && y === M - 1) {
                return "Yes";
            }

            for (const [dx, dy] of directions) {
                const nx = x + dx;
                const ny = y + dy;

                // Check boundary conditions and whether visited
                if (nx >= 0 && ny >= 0 && nx < N && ny < M && 
                    !visited[nx][ny] && grid[nx][ny] === 0) {
                    visited[nx][ny] = true;
                    queue.push([nx, ny]);
                }
            }
        }
        return "No";
    }

    const grid = [
        [0, 0, 1, 0],
        [0, 1, 0, 0],
        [0, 1, 1, 0],
        [0, 0, 0, 0]
    ];
    console.log(canReachDestination(grid)); // Result: "Yes"

Conclusion

Through this problem, we have solved a pathfinding problem using the BFS algorithm. In actual coding tests, you will often encounter such problems, so it is important to practice various algorithms to develop problem-solving skills for diverse challenges. In the next lesson, we will address different types of algorithm problems. Thank you!