{"id":33612,"date":"2024-11-01T09:18:29","date_gmt":"2024-11-01T09:18:29","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33612"},"modified":"2024-11-01T11:47:25","modified_gmt":"2024-11-01T11:47:25","slug":"python-coding-test-course-breadth-first-search","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33612\/","title":{"rendered":"python coding test course, breadth-first search"},"content":{"rendered":"

<\/p>\n

\n Breadth-First Search (BFS) is a method for exploring graphs or trees, starting from a vertex and visiting all its adjacent vertices first, followed by the unvisited adjacent vertices. It can also be used as a shortest path search algorithm in certain cases. Today, we will proceed with a deep problem-solving approach along with the basic concept of BFS.\n<\/p>\n

Problem: Numbering Complexes<\/h2>\n

Problem Description<\/h3>\n

\n In a given n x n array consisting of 0s and 1s, 1 represents the location of a house and 0 represents the absence of a house. Write a program that assigns each complex a unique number to distinguish all the houses. The size of a complex is defined as the number of houses belonging to it.\n<\/p>\n

Input<\/h3>\n
\nn (1 \u2264 n \u2264 25)\nAn n x n array composed of 0s and 1s\n<\/pre>\n
Output<\/h3>\n
\nPrint the size of each complex in ascending order\n<\/pre>\n
Example Input<\/h2>\n
\n7\n0 0 1 0 0 1 1\n0 0 1 0 1 1 1\n0 1 1 0 0 0 0\n0 0 0 0 1 0 0\n1 1 1 0 1 1 0\n0 0 0 0 0 0 0\n0 0 1 0 0 0 0\n<\/pre>\n
Example Output<\/h2>\n
\n1\n7\n<\/pre>\n
Problem Approach<\/h2>\n
\n    To solve this problem, we will use the BFS algorithm to explore the graph. By traversing the provided 2D array, whenever we encounter a house (1), we will count all the connected houses using BFS to calculate the size of the complex. In the next step, we will explain the concept of BFS in detail.\n<\/p>\n
Breadth-First Search (BFS) Concept<\/h2>\n
\n    BFS is implemented using a queue. It follows the following process:\n<\/p>\n
    \n
  1. Add the starting node to the queue and mark it as visited.<\/li>\n
  2. Remove a node from the queue and add all its adjacent nodes (that have not yet been visited) to the queue, marking them as visited.<\/li>\n
  3. If the queue is not empty, return to step 2.<\/li>\n<\/ol>\n
    Coding Implementation<\/h2>\n
    \n    I will write code to solve the problem using the BFS algorithm.\n<\/p>\n
    \nfrom collections import deque\n\ndef bfs(x, y, n, graph, visited):\n    queue = deque()\n    queue.append((x, y))\n    visited[x][y] = True\n\n    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n    size = 1  # store the size of the complex\n\n    while queue:\n        cx, cy = queue.popleft()  # current position\n        for dx, dy in directions:\n            nx, ny = cx + dx, cy + dy\n            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and graph[nx][ny] == 1:\n                visited[nx][ny] = True\n                queue.append((nx, ny))\n                size += 1  # increase the count of connected houses\n\n    return size  # return the size of the complex\n\ndef find_complexes(n, graph):\n    visited = [[False] * n for _ in range(n)]\n    complexes = []\n\n    for i in range(n):\n        for j in range(n):\n            if graph[i][j] == 1 and not visited[i][j]:\n                size = bfs(i, j, n, graph, visited)\n                complexes.append(size)\n\n    return sorted(complexes)  # return the sizes in ascending order\n\n# Example input\nn = 7\ngraph = [\n    [0, 0, 1, 0, 0, 1, 1],\n    [0, 0, 1, 0, 1, 1, 1],\n    [0, 1, 1, 0, 0, 0, 0],\n    [0, 0, 0, 0, 1, 0, 0],\n    [1, 1, 1, 0, 1, 1, 0],\n    [0, 0, 0, 0, 0, 0, 0],\n    [0, 0, 1, 0, 0, 0, 0]\n]\n\ncomplex_sizes = find_complexes(n, graph)\nprint(len(complex_sizes))  # print the number of complexes\nfor size in complex_sizes:\n    print(size)  # print the size of each complex\n<\/code><\/pre>\n
    Code Explanation<\/h2>\n
    \n    The above code demonstrates how to calculate the size of complexes using BFS. The main functions are find_complexes<\/code> and bfs<\/code>.\n<\/p>\n