1. Introduction to Depth-First Search (DFS)
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.
The operation of DFS is as follows:
- Add the starting node to the stack.
- Pop a node from the stack and explore it.
- Mark the explored node as visited.
- Add all unvisited adjacent nodes to the stack.
- Repeat the above process while the stack is not empty.
2. Problem Description
Problem: Counting the Number of Islands
In the given 2D array grid, ‘1’ represents land, and ‘0’ represents water.
An island is a set of connected lands vertically or horizontally.
Write a function to count the number of islands.
Input:
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
3. Problem Solving Process
3.1. Understanding the Problem
To solve the problem, we first need to identify the sections of connected land (i.e., islands).
Each island can be identified using DFS, by traversing the land and also exploring adjacent land,
thereby confirming all parts of the island.
3.2. Designing the Data Structure
We will use a stack to implement DFS.
To efficiently manage resources, we will use a boolean array to keep track of the visited status of all elements in the 2D array.
3.3. Implementing DFS
def dfs(grid, visited, i, j):
# Exit if out of bounds or already visited
if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or visited[i][j] or grid[i][j] == '0':
return
# Mark the current position as visited
visited[i][j] = True
# Explore up, down, left, right
dfs(grid, visited, i - 1, j) # Up
dfs(grid, visited, i + 1, j) # Down
dfs(grid, visited, i, j - 1) # Left
dfs(grid, visited, i, j + 1) # Right
3.4. Implementing the Final Function
def numIslands(grid):
if not grid:
return 0
visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
island_count = 0
# Explore all nodes in the grid
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1' and not visited[i][j]:
dfs(grid, visited, i, j)
island_count += 1 # Found a new island
return island_count
3.5. Testing the Code
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
print(numIslands(grid)) # Should print 3.
4. Review of Problem Solving
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.
Since we visit each node at most once, this can be considered an efficient method.
Additionally, the space complexity is also O(N * M), due to the additional space used for the visiting list.
While DFS can use a large amount of memory, it can often be more effective than BFS depending on the nature or size of the problem.
Particularly beneficial in pathfinding problems or problems distinguishing connected components, the advantages of DFS can be utilized.
5. Conclusion
In this lecture, we explored the basic concept of DFS and the problem-solving approach.
DFS can be applied to various problems, so based on this lecture, please try solving different issues.
Thank you.