BFS template
General BFS Template for State Exploration
1. Initialization:
- Define the problem space (e.g., grid, game state).
- Identify initial conditions (starting points, initial state).
- Set up the BFS queue (deque) and a set for visited states if applicable.
2. Define Valid Movements or Transitions:
- Determine how you can move or transition from one state to another.
- This could involve direct moves in a grid, or more complex state changes.
3. BFS Loop:
- Process each state in the queue.
- For each state, generate possible next states based on valid movements or transitions.
- Check each generated state for goal conditions or termination conditions.
- Add valid, non-visited states to the queue and mark as visited.
4. Goal Check:
- During state generation, continuously check if the current state meets the goal criteria.
- Terminate early if the goal is achieved or if certain conditions are met (like exceeding move limits).
5. Final Outcome:
- Return the result based on whether the goal was achieved or the state space was exhaustively searched without success.
Code Template
from collections import deque
def bfs_solve(start_conditions):
# BFS Initialization
queue = deque([start_conditions])
visited = set([start_conditions])
directions = [...] # Define directions or transitions based on the problem
while queue:
current_state = queue.popleft()
# Check if current state is the goal state
if is_goal_state(current_state):
return True # or return count, path, etc.
# Generate all possible next states
for direction in directions:
next_state = move(current_state, direction)
if is_valid_state(next_state) and next_state not in visited:
visited.add(next_state)
queue.append(next_state)
# Optional: check for other conditions to stop or modify the search
return False # If the loop ends without finding the goal
def is_goal_state(state):
# Implement logic to determine if the state is a goal state
pass
def move(state, direction):
# Implement how to transition from state to next state using direction
pass
def is_valid_state(state):
# Check if the state is valid (not out of bounds, not blocked, etc.)
pass
# Usage example with pseudo-code for a specific problem
# start_conditions = (initial_position, other_necessary_conditions)
# result = bfs_solve(start_conditions)
# print(result)
Customizing the Template
For any specific BFS problem:
- Define the directions or possible state transitions based on the problem (e.g., movement in a grid, configurations in a puzzle).
- Implement the is_goal_state, move, and is_valid_state functions to handle the specific logic of what constitutes a goal, how to move from one state to another, and what makes a state valid or invalid in the context of the problem.
- Handle special cases or additional rules within the BFS loop as needed by the problem specifications.
Note:
the use of a visited set was replaced by directly modifying the tomato_data grid.
Examples:
Q. 로봇 청소기
This problem involves a robot vacuum cleaner that cleans each accessible cell in a grid-based room, rotating and moving based on specific rules.
from collections import deque
def get_d_index_when_rotate_to_left(d):
return (d + 3) % 4
def bfs_robot_vacuum(start_r, start_c, start_d, room_map):
n, m = len(room_map), len(room_map[0])
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)] # North, East, South, West
queue = deque([(start_r, start_c, start_d)])
visited = set([(start_r, start_c)])
while queue:
r, c, d = queue.popleft()
cleaned = False
for _ in range(4):
d = get_d_index_when_rotate_to_left(d)
next_r, next_c = r + directions[d][0], c + directions[d][1]
if 0 <= next_r < n and 0 <= next_c < m and room_map[next_r][next_c] == 0 and (next_r, next_c) not in visited:
visited.add((next_r, next_c))
queue.append((next_r, next_c, d))
cleaned = True
break
if not cleaned:
back_r, back_c = r - directions[d][0], c - directions[d][1]
if 0 <= back_r < n and 0 <= back_c < m and room_map[back_r][back_c] != 1:
queue.append((back_r, back_c, d))
return len(visited)
# Usage:
current_room_map = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
...
]
print(bfs_robot_vacuum(7, 4, 0, current_room_map)) # Output will be the number of cleaned cellsQ. 구슬탈출
This problem involves simulating the movement of two marbles on a board, aiming to drop the red marble into a hole without the blue one falling in.
from collections import deque
def is_available_to_take_out_only_red_marble(game_map):
n = len(game_map)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # Up, down, left, right
queue = deque()
visited = set()
rx, ry, bx, by = -1, -1, -1, -1
for i in range(n):
for j in range(n):
if game_map[i][j] == "R":
rx, ry = i, j
elif game_map[i][j] == "B":
bx, by = i, j
queue.append((rx, ry, bx, by, 0))
visited.add((rx, ry, bx, by))
def move_until_blocked(x, y, dx, dy):
steps = 0
while game_map[x + dx][y + dy] != '#' and game_map[x][y] != 'O':
x += dx
y += dy
steps += 1
return x, y, steps
while queue:
rx, ry, bx, by, moves = queue.popleft()
if moves > 10:
break
for dx, dy in directions:
new_rx, new_ry, r_steps = move_until_blocked(rx, ry, dx, dy)
new_bx, new_by, b_steps = move_until_blocked(bx, by, dx, dy)
if game_map[new_bx][new_by] == 'O':
continue
if game_map[new_rx][new_ry] == 'O':
return True
if new_rx == new_bx and new_ry == new_by:
if r_steps > b_steps:
new_rx -= dx
new_ry -= dy
else:
new_bx -= dx
new_by -= dy
if (new_rx, new_ry, new_bx, new_by) not in visited:
visited.add((new_rx, new_ry, new_bx, new_by))
queue.append((new_rx, new_ry, new_bx, new_by, moves + 1))
return False
# Usage:
game_map = [
["#", "#", "#", "#", "#"],
["#", ".", ".", "B", "#"],
["#", ".", "#", ".", "#"],
["#", "R", "O", ".", "#"],
["#", "#", "#", "#", "#"],
]
print(is_available_to_take_out_only_red_marble(game_map)) # True or False based on the game map
