BFS advanced
Multiple places to start, individually do bfs
- Make bfs function (start, grid, visited)
def bfs(start, grid, visited, n):
queue = deque([(start[0], start[1])])
visited[start[0]][start[1]] = True
house_count = 0
directions = [(-1,0), (1,0), (0, 1), (0, -1)]
while queue:
r, c = queue.popleft()
house_count += 1
for direction in directions:
next_r, next_c = r + direction[0], c + direction[1]
if 0 <= next_r < n and 0 <= next_c < n and not visited[next_r][next_c]:
if grid[next_r][next_c] == 1:
visited[next_r][next_c] = True
queue.append((next_r, next_c))
return house_count- In main function, find start points doing loop
for i in range(n):
for j in range(n):
if apartments[i][j] == 1 and not visited[i][j]:
count = bfs((i, j), apartments, visited, n)
house_counts.append(count)
example code 1 (problem for apartments)
from collections import deque
# 1. Loop through each cell in the grid.
# 2. If the cell contains a house (i.e., 1) and has not been visited yet, initiate a BFS from that cell.
# 3. Store the count of houses in each cluster found by the BFS.
# WHY? you have to perform multiple BFS
# bfs with multiple start points is for when in the end, they should be considered together like tomato problem
def bfs(start, grid, visited, n):
queue = deque([(start[0], start[1])])
visited[start[0]][start[1]] = True
house_count = 0
directions = [(-1,0), (1,0), (0, 1), (0, -1)]
while queue:
r, c = queue.popleft()
house_count += 1
for direction in directions:
next_r, next_c = r + direction[0], c + direction[1]
if 0 <= next_r < n and 0 <= next_c < n and not visited[next_r][next_c]:
if grid[next_r][next_c] == 1:
visited[next_r][next_c] = True
queue.append((next_r, next_c))
return house_count
n = int(input())
apartments = []
# this does NOT work since there is no space between the input map
# for i in range(n):
# row = map(int, input().split())
# print(row)
for i in range(n):
row = input().strip() # read each row as a string
apartments.append([int(char) for char in row])
visited = [[False] * n for _ in range(n)]
house_counts = []
for i in range(n):
for j in range(n):
if apartments[i][j] == 1 and not visited[i][j]:
count = bfs((i, j), apartments, visited, n)
house_counts.append(count)
house_counts.sort()
print(len(house_counts))
for i in house_counts:
print(i)
example code 2 (problem for cabbage)
from collections import deque
def bfs(start, grid, visited):
queue = deque([(start[0], start[1])])
visited.add((start[0], start[1]))
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while queue:
r, c = queue.popleft()
for direction in directions:
new_r, new_c = r + direction[0], c + direction[1]
if 0 <= new_r < n and 0 <= new_c < m and (new_r, new_c) not in visited:
if grid[new_r][new_c] == 1:
queue.append((new_r, new_c))
visited.add((new_r, new_c))
return 1
test_cases = int(input())
for test_case in range(test_cases):
m, n, total_cabbage = map(int, input().split())
grid = [[0] * m for _ in range(n)]
for i in range(total_cabbage):
x, y = map(int, input().split())
grid[y][x] = 1
visited = set([])
total_worm = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 1 and (i, j) not in visited:
total_worm += bfs((i, j), grid, visited)
print(total_worm)
Note:
for i in range(n): for j in range(m): if grid[i][j] == 1 and (i, j) not in visited: total_worm += bfs((i, j), grid, visited)
One BFS, multiple layers
3d bfs: when you have multiple layers but all inter-connected in the end + Multiple start position (add all to queue before doing bfs)
example code (problem for 3d tomato)
from collections import deque
m, n, h = map(int,(input().split()))
queue = deque([])
tomato_data = []
for height in range(h):
layer = []
for i in range(n):
row = list(map(int, input().split()))
layer.append(row)
# Check for the presence of 1 in the row
for j in range(m):
if row[j] == 1:
queue.append((j, i, height, 0)) # (col, row, height)
tomato_data.append(layer)
# (x, y, z) for 3d & (row, col) for 2d
# 동 서 남 북 위 아래
directions = [(1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, 1), (0, 0, -1)]
day_count = 0
while queue:
c, r, z, day = queue.popleft()
day_count = day
for direction in directions:
next_c, next_r, next_z = c + direction[0], r + direction[1], z + direction[2]
if 0 <= next_c < m and 0 <= next_r < n and 0 <= next_z < h:
if tomato_data[next_z][next_r][next_c] == 0:
tomato_data[next_z][next_r][next_c] = 1
queue.append((next_c, next_r, next_z, day + 1))
def check_result(tomato_data):
for layer in tomato_data:
for row in layer:
if 0 in row:
return -1
return day_count
print(check_result((tomato_data)))
# NOTE:
# how you add queue vs how tomato_data is are different
# tomato data (height, row, col)
# queue and direction calculation = (col, row, height)Note:
- (row, col) for 2d
- (x, y, z) for 3d
How you add to queue VS. how grid looks like (reverse)
grid: row, col
queue: (x, y) where x is col, y is row
