The programming language Swift is widely used in the Apple ecosystem and is often utilized for iOS and macOS application development.
It is important for developers to have problem-solving skills for algorithms. Especially for employment, it is necessary to demonstrate
the ability to solve various problems. Today, we will look into the maze exploration problem. To solve this problem, we will compare
the Depth-First Search (DFS) algorithm and the Breadth-First Search (BFS) algorithm.
Problem Definition
The problem is to find the shortest path from the starting point to the destination in a maze represented by a given 2D array.
The maze consists of 0s and 1s, where 0 represents a traversable space and 1 represents a wall.
The starting point is (0, 0) and the destination is (n-1, m-1).
Here is an example maze:
0 0 1 0 0
1 0 1 0 1
0 0 0 0 1
0 1 1 0 0
0 0 0 0 0
Input Format
A 2D array of size n x m is inputted. The array consists of 0s and 1s.
Output Format
The length of the shortest path from the starting point to the destination is outputted. If it is not reachable, -1 is outputted.
Approach to Solve the Problem
Various search algorithms can be used to solve this problem. Among them,
Depth-First Search (DFS) and Breadth-First Search (BFS) are the most commonly used.
BFS is suitable for shortest path problems. I will provide a brief explanation of each algorithm.
BFS (Breadth-First Search)
BFS visits all vertices of a graph level by level. It visits all adjacent vertices from the starting vertex,
then explores adjacent vertices in the next step to explore all paths. BFS is implemented using a queue,
and it can find the shortest path by recording the depth of the path each time a vertex is visited. The time complexity of BFS is O(V + E).
DFS (Depth-First Search)
DFS starts at one vertex of the graph and explores as deeply as possible before backtracking to explore alternative paths.
DFS is implemented using a stack, and the order of visiting depends on the depth. Since DFS explores all paths, it does not guarantee
the shortest path. Therefore, BFS is more suitable for maze exploration problems. The time complexity of DFS is O(V + E),
and its space complexity is O(V).
Algorithm Design
Now, let’s design an algorithm to solve the maze exploration problem using BFS.
We need to define and initialize the necessary variables to proceed to the next steps.
// maze size n, m
let n = maze.count
let m = maze[0].count
// direction array (up, down, left, right)
let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
var queue: [(Int, Int)] = []
// add starting point (0, 0) to queue
queue.append((0, 0))
// visited array
var visited = Array(repeating: Array(repeating: false, count: m), count: n)
visited[0][0] = true
// distance array
var distance = Array(repeating: Array(repeating: -1, count: m), count: n)
distance[0][0] = 0
Code Implementation
Let’s solve the problem with code. Below is the BFS algorithm implemented in Swift.
func bfs(maze: [[Int]]) -> Int {
let n = maze.count
let m = maze[0].count
let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
var queue: [(Int, Int)] = []
var visited = Array(repeating: Array(repeating: false, count: m), count: n)
var distance = Array(repeating: Array(repeating: -1, count: m), count: n)
queue.append((0, 0))
visited[0][0] = true
distance[0][0] = 0
while !queue.isEmpty {
let (x, y) = queue.removeFirst()
for direction in directions {
let newX = x + direction.0
let newY = y + direction.1
if newX >= 0 && newY >= 0 && newX < n && newY < m &&
maze[newX][newY] == 0 && !visited[newX][newY] {
visited[newX][newY] = true
distance[newX][newY] = distance[x][y] + 1
queue.append((newX, newY))
}
}
}
return distance[n-1][m-1] != -1 ? distance[n-1][m-1] : -1
}
let maze = [
[0, 0, 1, 0, 0],
[1, 0, 1, 0, 1],
[0, 0, 0, 0, 1],
[0, 1, 1, 0, 0],
[0, 0, 0, 0, 0]
]
let result = bfs(maze: maze)
print(result) // Result: 8
Code Explanation
In the above code, we used the BFS algorithm to explore the maze and find the shortest path.
Initially, we start at the coordinate (0, 0), and set up the queue, visited array, and distance array.
When we dequeue one coordinate from the queue, we check all adjacent coordinates. If it is a traversable coordinate, we add it to the queue and update the
visited array and distance array. Finally, we return the distance value of the destination point.
If it is unreachable, we return -1.
Conclusion
In this tutorial, we learned how to solve the maze exploration problem with Swift.
Through the BFS algorithm, we effectively utilized the queue and dimensional arrays to find the shortest path.
Such search algorithms are often encountered in job interviews, so we need to practice sufficiently to solve a variety of problems.
These fundamental concepts are very useful when solving algorithm problems in Swift.