Kotlin coding test course, depth-first search

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.

1. Test Case 1:
   Input:

   [[1,1,0,0],[0,1,0,0],[0,0,0,1],[1,0,0,1]]

   Expected Output: 2

2. Test Case 2:
   Input:

   [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]

   Expected Output: 0

3. 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.