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.<\/p>\n
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’.<\/p>\n
The basic operation of BFS is as follows:<\/p>\n
Now, let\u2019s understand BFS through a problem that is likely to come up in a real coding test.<\/p>\n
We have an array of size n \u00d7 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.<\/p>\n
\n5\n01101\n11011\n11100\n00011\n00000\n<\/pre>\nOutput<\/h4>\n
\n3\n2\n1\n<\/pre>\n5. C# Code Implementation<\/h2>\n
Below is the C# code written to solve this problem using BFS.<\/p>\n
\nusing System;\nusing System.Collections.Generic;\n\nclass Program\n{\n static int n;\n static int[,] map;\n static bool[,] visited;\n static int[] dx = { 1, -1, 0, 0 };\n static int[] dy = { 0, 0, 1, -1 };\n\n static void Main()\n {\n n = int.Parse(Console.ReadLine());\n map = new int[n, n];\n visited = new bool[n, n];\n\n for (int i = 0; i < n; i++)\n {\n string line = Console.ReadLine();\n for (int j = 0; j < n; j++)\n {\n map[i, j] = line[j] - '0';\n }\n }\n\n Listresults = new List ();\n\n for (int i = 0; i < n; i++)\n {\n for (int j = 0; j < n; j++)\n {\n if (map[i, j] == 1 && !visited[i, j])\n {\n results.Add(BFS(i, j));\n }\n }\n }\n\n results.Sort();\n Console.WriteLine(results.Count);\n foreach (int count in results)\n {\n Console.WriteLine(count);\n }\n }\n\n static int BFS(int startX, int startY)\n {\n Queue<(int, int)> queue = new Queue<(int, int)>();\n queue.Enqueue((startX, startY));\n visited[startX, startY] = true;\n\n int count = 0;\n\n while (queue.Count > 0)\n {\n var (x, y) = queue.Dequeue();\n count++;\n\n for (int i = 0; i < 4; i++)\n {\n int nx = x + dx[i];\n int ny = y + dy[i];\n\n if (nx >= 0 && ny >= 0 && nx < n && ny < n && map[nx, ny] == 1 && !visited[nx, ny])\n {\n queue.Enqueue((nx, ny));\n visited[nx, ny] = true;\n }\n }\n }\n\n return count;\n }\n}\n<\/int><\/int><\/code><\/pre>\n 6. Code Explanation<\/h2>\n
The C# code above works as follows:<\/p>\n
\n
- It receives n as input and stores the house placement information in a 2D array of size n \u00d7 n.<\/li>\n
- The visited array records whether each house has been visited.<\/li>\n
- Nesting for loops are used to explore all houses, executing BFS only for unvisited houses.<\/li>\n
- The BFS method uses a queue to explore connected houses from the starting point and counts the number of connected houses.<\/li>\n
- It stores the sizes of all complexes in a list, sorts them, and then outputs them.<\/li>\n<\/ol>\n
7. Conclusion<\/h2>\n
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.<\/p>\n
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!<\/p>\n