Introduction
Hello! In this post, we will explore the Depth-First Search (DFS) algorithm. DFS is a search algorithm used in graph or tree structures that explores as deeply as possible before backtracking to adjacent nodes. It is a crucial topic often featured in coding tests; therefore, I recommend mastering it to enhance your understanding of algorithms and your problem-solving skills.
Problem Description
Problem Title: Number of Islands
In the given 2D array, ‘1’ represents land and ‘0’ represents water. Continuous ‘1’s are considered a single island. All ‘1’s that are connected horizontally or vertically to land ‘1’ are part of the same island. Calculate the number of islands in the given array.
Input Example
[
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[1, 0, 1, 0, 1]
]Output Example
Number of islands: 5
Solution Process
This problem can be solved using the DFS algorithm. Let’s go through the steps to solve the problem.
Step 1: Graph Representation
The problem deals with a graph represented as a 2D array. Each ‘1’ represents land, and to solve this problem, we need to determine how these lands are connected.
Step 2: Implementing the DFS Algorithm
When visiting each land ‘1’ using DFS, we need to group them as a single island. To do this, we define a recursive function to visit adjacent land ‘1’s.
Step 3: Writing the Code
Now, let’s write code to implement the basic DFS algorithm. We can implement it using Kotlin as follows.
fun numIslands(grid: Array): Int {
if (grid.isEmpty()) return 0
var count = 0
fun dfs(i: Int, j: Int) {
if (i < 0 || i >= grid.size || j < 0 || j >= grid[0].size || grid[i][j] == '0') {
return
}
grid[i][j] = '0' // Mark as visited
dfs(i - 1, j) // up
dfs(i + 1, j) // down
dfs(i, j - 1) // left
dfs(i, j + 1) // right
}
for (i in grid.indices) {
for (j in grid[i].indices) {
if (grid[i][j] == '1') {
count++
dfs(i, j) // new island found
}
}
}
return count
} Step 4: Code Explanation
In the above code, the numIslands function takes a 2D array as a parameter and returns the number of islands.
The internal dfs function recursively visits each land, changing already visited lands to ‘0’ to prevent duplicate visits.
The double loop checks each element of the array, increasing the island count whenever a ‘1’ is found and calling dfs.
Step 5: Time Complexity and Space Complexity
The time complexity of the DFS algorithm is O(M * N), where M is the number of rows and N is the number of columns.
The space complexity is O(H), where H is the depth of the recursive call stack. In the worst case, it can be O(M + N).
Test Case Analysis
We have written a basic code based on the above description, but it is important to verify the accuracy of the code through various test cases.
Here are descriptions of some test cases.
-
Test Case 1:
Input:[[1,1,0,0],[0,1,0,0],[0,0,0,1],[1,0,0,1]]Expected Output: 2
-
Test Case 2:
Input:[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]Expected Output: 0
-
Test Case 3:
Input:[[1,1,1,1],[1,0,0,0],[1,1,1,1]]Expected Output: 1
Conclusion
In this post, we explained Depth-First Search (DFS) and implemented the algorithm through a sample problem.
DFS is a very useful tool when solving graph problems, so you will often encounter it in coding tests.
Practice solving various problems to understand and utilize DFS in depth.