C# Coding Test Course, Breadth-First Search

Hello, everyone! Today, we will take a deep dive into one of the important algorithms dealt with in coding tests using C#, which is Breadth-First Search (BFS). BFS is an algorithm for exploring graph or tree data structures, and it is useful for solving shortest path problems or finding specific nodes.

1. What is Breadth-First Search (BFS)?

BFS is a search algorithm implemented using the Queue data structure. This algorithm starts from a given node, explores all the adjacent nodes to that node, and then continues to explore the adjacent nodes of the nodes it has just explored. This approach gradually explores wider areas, hence the name ‘Breadth-First’.

2. Characteristics of BFS

• Shortest path exploration: BFS is suitable for finding the shortest path when all edge weights are the same.
• Sunlight exploration: BFS visits closer nodes first, exploring in a way that can be likened to sunlight shining.
• Uses a queue: It uses a queue to store the order of exploration, managing the nodes to be visited in a FIFO (First In First Out) manner.

3. How BFS Works

The basic operation of BFS is as follows:

1. Add the starting node to the queue and mark it as visited.
2. Remove a node from the queue and check all its adjacent nodes.
3. If an adjacent node has not been visited yet, add it to the queue and mark it as visited.
4. Repeat steps 2 and 3 until the queue is empty.

4. Problem Solving

Now, let’s understand BFS through a problem that is likely to come up in a real coding test.

Problem: ‘Labeling Complexes’

We have an array of size n × n consisting of 0s and 1s. Here, 1 indicates where a house exists, and 0 indicates where there are no houses. We consider connected houses as a single complex, and we will use BFS to label the complexes. The problem is to count the number of houses belonging to the same complex and output the size of each complex.

Input

5
01101
11011
11100
00011
00000

Output

3
2
1

5. C# Code Implementation

Below is the C# code written to solve this problem using BFS.

using System;
using System.Collections.Generic;

class Program
{
    static int n;
    static int[,] map;
    static bool[,] visited;
    static int[] dx = { 1, -1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };

    static void Main()
    {
        n = int.Parse(Console.ReadLine());
        map = new int[n, n];
        visited = new bool[n, n];

        for (int i = 0; i < n; i++)
        {
            string line = Console.ReadLine();
            for (int j = 0; j < n; j++)
            {
                map[i, j] = line[j] - '0';
            }
        }

        List results = new List();

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (map[i, j] == 1 && !visited[i, j])
                {
                    results.Add(BFS(i, j));
                }
            }
        }

        results.Sort();
        Console.WriteLine(results.Count);
        foreach (int count in results)
        {
            Console.WriteLine(count);
        }
    }

    static int BFS(int startX, int startY)
    {
        Queue<(int, int)> queue = new Queue<(int, int)>();
        queue.Enqueue((startX, startY));
        visited[startX, startY] = true;

        int count = 0;

        while (queue.Count > 0)
        {
            var (x, y) = queue.Dequeue();
            count++;

            for (int i = 0; i < 4; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && ny >= 0 && nx < n && ny < n && map[nx, ny] == 1 && !visited[nx, ny])
                {
                    queue.Enqueue((nx, ny));
                    visited[nx, ny] = true;
                }
            }
        }

        return count;
    }
}

6. Code Explanation

The C# code above works as follows:

1. It receives n as input and stores the house placement information in a 2D array of size n × n.
2. The visited array records whether each house has been visited.
3. Nesting for loops are used to explore all houses, executing BFS only for unvisited houses.
4. The BFS method uses a queue to explore connected houses from the starting point and counts the number of connected houses.
5. It stores the sizes of all complexes in a list, sorts them, and then outputs them.

7. Conclusion

In this lecture, we explored how to solve problems in coding tests using Breadth-First Search (BFS). BFS is a powerful tool applicable to various problems. Understanding BFS is crucial in situations like exploring graphs or finding the shortest path.

Continue to build your skills by practicing BFS with examples and tackling more complex problems. If you have any questions or comments, feel free to leave them in the comments. In the next session, we will cover another algorithm!