1. Introduction to Depth-First Search (DFS)<\/h2>\n
\n Depth-First Search (DFS) is one of the graph exploration algorithms that explores as deep as possible from a given node and, when there are no more nodes to explore, backtracks to the last visited node to explore other paths. This method is used for various purposes depending on the structure of the graph and is applied in tree traversal, connected component exploration, pathfinding problems, and more.\n <\/p>\n
\n The operation of DFS is as follows:<\/p>\n
- \n
- Add the starting node to the stack.<\/li>\n
- Pop a node from the stack and explore it.<\/li>\n
- Mark the explored node as visited.<\/li>\n
- Add all unvisited adjacent nodes to the stack.<\/li>\n
- Repeat the above process while the stack is not empty.<\/li>\n<\/ul>\n<\/section>\n
\n 2. Problem Description<\/h2>\n
Problem: Counting the Number of Islands<\/h3>\n
\n In the given 2D array grid, ‘1’ represents land, and ‘0’ represents water.
\n An island is a set of connected lands vertically or horizontally.
\n Write a function to count the number of islands.\n <\/p>\n\n Input: \n grid = [\n [\"1\",\"1\",\"0\",\"0\",\"0\"],\n [\"1\",\"1\",\"0\",\"0\",\"0\"],\n [\"0\",\"0\",\"1\",\"0\",\"0\"],\n [\"0\",\"0\",\"0\",\"1\",\"1\"]\n ]\n Output: 3\n <\/pre>\n<\/section>\n
\n 3. Problem Solving Process<\/h2>\n
3.1. Understanding the Problem<\/h3>\n
\n To solve the problem, we first need to identify the sections of connected land (i.e., islands).
\n Each island can be identified using DFS, by traversing the land and also exploring adjacent land,
\n thereby confirming all parts of the island.\n <\/p>\n3.2. Designing the Data Structure<\/h3>\n
\n We will use a stack to implement DFS.
\n To efficiently manage resources, we will use a boolean array to keep track of the visited status of all elements in the 2D array.\n <\/p>\n3.3. Implementing DFS<\/h3>\n
\n def dfs(grid, visited, i, j):\n # Exit if out of bounds or already visited\n if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or visited[i][j] or grid[i][j] == '0':\n return\n # Mark the current position as visited\n visited[i][j] = True\n \n # Explore up, down, left, right\n dfs(grid, visited, i - 1, j) # Up\n dfs(grid, visited, i + 1, j) # Down\n dfs(grid, visited, i, j - 1) # Left\n dfs(grid, visited, i, j + 1) # Right\n <\/pre>\n
3.4. Implementing the Final Function<\/h3>\n
\n def numIslands(grid):\n if not grid:\n return 0\n \n visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]\n island_count = 0\n \n # Explore all nodes in the grid\n for i in range(len(grid)):\n for j in range(len(grid[0])):\n if grid[i][j] == '1' and not visited[i][j]:\n dfs(grid, visited, i, j)\n island_count += 1 # Found a new island\n \n return island_count\n <\/pre>\n
3.5. Testing the Code<\/h3>\n
\n grid = [\n [\"1\",\"1\",\"0\",\"0\",\"0\"],\n [\"1\",\"1\",\"0\",\"0\",\"0\"],\n [\"0\",\"0\",\"1\",\"0\",\"0\"],\n [\"0\",\"0\",\"0\",\"1\",\"1\"]\n ]\n\n print(numIslands(grid)) # Should print 3.\n <\/pre>\n<\/section>\n
\n 4. Review of Problem Solving<\/h2>\n
\n We solved the problem using DFS, with a time complexity of O(N * M), where N is the number of rows and M is the number of columns.
\n Since we visit each node at most once, this can be considered an efficient method.
\n Additionally, the space complexity is also O(N * M), due to the additional space used for the visiting list.\n <\/p>\n