Swift Coding Test Course, Breadth-First Search

1. Introduction

Breadth-First Search (BFS) is an algorithm for traversing nodes in a graph or tree structure.
BFS explores adjacent nodes first from the starting node, then examines the adjacent nodes of those nodes,
visiting all levels of nodes in order. This method is useful for finding the shortest path since it explores
the graph or tree level by level and can be applied to many problems.

2. Problem Description

        4 4
        0 0 1 0
        0 1 0 0
        2 0 1 0
        0 0 3 0
        

        7
        

3. Problem Analysis

BFS can be used to solve this problem.
BFS is suitable for finding the shortest path, starting from the starting point (2) in the given grid and
exploring the path to the destination (3) by moving to adjacent walkable areas (0).
Possible directions for movement are limited to four: up, down, left, and right.

One of the features of BFS is that it adds each node to the queue, allowing it to search in level order.
This makes it easy to count the number of moves needed to reach a specific node.
This method can be used to explore all 0s and 3s filled in the grid to check whether the destination can be reached.

4. Algorithm Design

1. **Initialize the grid and objects**: Initialize the queue for breadth-first search and a visited array based on the input grid.
2. **Add the starting point to the queue**: Add the starting point to the queue and update the visited array.
3. **Execute BFS**: For each node removed from the queue, check its four neighbors.
If the neighbor is walkable, add it to the queue and mark it as visited.
4. **Check for reaching the destination**: If the destination is reached, output the number of moves at that point.
5. **Handle cases where destination is unreachable**: If the queue is empty but the destination has not been reached, output -1.

5. Code Implementation

Now, we will implement BFS in Swift based on the above algorithm design.

import Foundation

func findShortestPath(grid: [[Int]], start: (Int, Int), end: (Int, Int)) -> Int {
    let directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    var queue: [(Int, Int, Int)] = [(start.0, start.1, 0)] // (x, y, distance)
    var visited = grid
    visited[start.0][start.1] = 1 // Mark as visited

    while !queue.isEmpty {
        let (x, y, distance) = queue.removeFirst()
        
        // If reached the destination
        if (x, y) == end {
            return distance
        }

        // Explore neighboring nodes
        for direction in directions {
            let newX = x + direction.0
            let newY = y + direction.1
            
            // If within valid range and walkable
            if newX >= 0, newY >= 0, newX < grid.count, newY < grid[0].count, visited[newX][newY] == 0 {
                queue.append((newX, newY, distance + 1))
                visited[newX][newY] = 1 // Mark as visited
            }
        }
    }
    
    // If destination is not reached
    return -1
}

// Example input
let grid: [[Int]] = [
    [0, 0, 1, 0],
    [0, 1, 0, 0],
    [2, 0, 1, 0],
    [0, 0, 3, 0]
]

if let start = grid.enumerated().flatMap({ $0.element.enumerated().compactMap { $1 == 2 ? ($0.offset, $0.element) : nil } }).first,
   let end = grid.enumerated().flatMap({ $0.element.enumerated().compactMap { $1 == 3 ? ($0.offset, $0.element) : nil } }).first {
    let result = findShortestPath(grid: grid, start: start, end: end)
    print(result) // Output the minimum number of moves
}

6. Code Explanation

The code above finds the starting point and destination in the given grid and then
performs breadth-first search to find the shortest path.

• The four directions for exploration are defined as up, down, left, and right.
• A visited array is used to ensure that
  already visited nodes are not added to the queue again.
• When the destination is reached, the current distance is returned.
• If the destination cannot be reached, it returns -1.

7. Conclusion

Breadth-First Search (BFS) is a highly useful algorithm for solving shortest path problems.
It works efficiently in structures like 2D grids and frequently appears in various programming challenges.
It is important to practice different types of BFS problems to enhance understanding of the algorithm and problem-solving skills.
Through this tutorial, we hope you have gained a fundamental understanding of BFS and learned how to solve actual problems.

8. Additional Practice Problems

Try your hand at the following variant problems:

• Reach the destination while avoiding obstacles (1) using only a specific path in the given grid.
• Finding the shortest paths between multiple starting and ending points.
• Finding the shortest path when diagonal movements are also allowed, instead of only grid movements.

Tackling these problems will further enhance your understanding of the breadth-first search algorithm and improve your problem-solving abilities.