Introduction<\/h2>\n
\n 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.\n <\/p>\n<\/section>\n \n 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.\n <\/p>\n Number of islands: 5<\/p>\n<\/section>\n This problem can be solved using the DFS algorithm. Let’s go through the steps to solve the problem.<\/p>\n \n 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.\n <\/p>\n \n 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.\n <\/p>\n \n Now, let’s write code to implement the basic DFS algorithm. We can implement it using Kotlin as follows.\n <\/p>\n \n In the above code, the \n 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. \n 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.Problem Description<\/h2>\n
Problem Title: Number of Islands<\/h3>\n
Input Example<\/h3>\n
[\n [1, 1, 0, 0, 0],\n [0, 1, 0, 0, 1],\n [1, 0, 0, 1, 1],\n [0, 0, 0, 0, 0],\n [1, 0, 1, 0, 1]\n]<\/code><\/pre>\nOutput Example<\/h3>\n
Solution Process<\/h2>\n
Step 1: Graph Representation<\/h3>\n
Step 2: Implementing the DFS Algorithm<\/h3>\n
Step 3: Writing the Code<\/h3>\n
fun numIslands(grid: ArrayStep 4: Code Explanation<\/h3>\n
numIslands<\/code> function takes a 2D array as a parameter and returns the number of islands.
\n The internal dfs<\/code> function recursively visits each land, changing already visited lands to ‘0’ to prevent duplicate visits.
\n The double loop checks each element of the array, increasing the island count whenever a ‘1’ is found and calling dfs<\/code>.\n <\/p>\nStep 5: Time Complexity and Space Complexity<\/h3>\n
\n 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).\n <\/p>\nTest Case Analysis<\/h2>\n
\n Here are descriptions of some test cases.\n <\/p>\n