deque-based BFS, shortest paths and grid traversal
Part 4: Graph Foundations3 min readFree lesson
Part 04 – Graph Basics | Difficulty: ⭐⭐⭐☆☆
Introduction: Search That Guarantees the Shortest Path
BFS (Breadth-First Search) explores nodes closest to the start point first.
It is the only simple algorithm that guarantees the shortest path in an unweighted graph.
DFS vs BFS: When to Use?
Purpose
Recommendation
Shortest path (no weights)
BFS
Connected components / Backtracking
DFS
Convenience for recursive implementation
DFS
Need for layer-by-layer search
BFS
Learning Goals
Implement BFS using collections.deque.
Record the shortest distance with a distance array (dist[]) and reconstruct the path.
#Method 1: visited array
visited[node] = True #Only visit status
#Method 2: dist array (distance record + also serves as visit status)
dist = [-1] * (n + 1)
dist[start] = 0
if dist[nxt] == -1: #-1 = not visited
dist[nxt] = dist[node] + 1
Time/Space Complexity
Time: O(V + E)
Space: O(V) — queue + visited array
Example
File
Contents
src/01_bfs_basic.py
BFS base template, search order and distance
src/02_bfs_shortest_path.py
Shortest path dist array, path reconstruction
src/03_bfs_grid.py
Grid BFS: shortest path in a maze
src/04_bfs_multi_source.py
Multi-source BFS
5 Common Mistakes
Mistake of setting visited when dequeuing
#Wrong method: mark visited after pop
while queue:
node = queue.popleft()
if visited[node]: continue
visited[node] = True
#→ The same node can enter the queue multiple times
#Correct method: mark visited when pushing
queue.append(start)
visited[start] = True
while queue:
node = queue.popleft()
for nxt in graph[node]:
if not visited[nxt]:
visited[nxt] = True
queue.append(nxt)
Using list.pop(0) (O(n) operation)
Removing from the front of a list is O(n) → whole queue becomes O(n²)
Always use popleft() of collections.deque
Omitting grid range check
Always check range after nr, nc = r + dr, c + dc
Initializing start point distance to 1 instead of 0
Start point is already there, so distance is 0
dist[start] = 0
In multi-start BFS, not inserting all start points into the queue
#Wrong: BFS each starting point separately
#Correct: Put all starting points in the queue from the beginning
queue = deque()
for src in sources:
queue.append(src)
dist[src] = 0
Summary
Purpose
BFS Pattern
Simple visit order
deque + visited
Shortest distance
deque + dist[]
Grid exploration
4 directions + range check
Multi-start points
insert all into initial queue
Layer separation
layer boundary by queue size
Try It Yourself
Calculate the shortest distance in a 5×5 maze using BFS and backtrack the path.
Simulate "fire spreading from multiple flames" using multi-start BFS.
Write code to determine if a graph is bipartite using BFS.
Example files
The runnable files used in this lesson. Copy them into your own project and experiment.
src/01_bfs_basic.pyPython
"""Topic : BFS Basics — Search Order, Distance Array
Time : O(V + E)
Space : O(V)"""
from collections import deque
#── Basic BFS ─────────────────────────────────────────────────────────────────
def bfs(
graph: list[list[int]],
start: int,
n: int,
) -> tuple[list[int], list[int]]:
"""BFS Search.
Returns:
(Visit order, shortest distance array)
dist[i] = shortest distance from start → i (-1 if unreachable)"""
dist = [-1] * (n + 1)
dist[start] = 0
queue: deque[int] = deque([start])
order: list[int] = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
if dist[nxt] == -1:
dist[nxt] = dist[node] + 1
queue.append(nxt)
return order, dist
def bfs_verbose(
graph: list[list[int]],
start: int,
n: int,
) -> None:
"""BFS Output by Layer."""
dist = [-1] * (n + 1)
dist[start] = 0
queue: deque[int] = deque([start])
layer = 0
print(f"Layer {layer}: [{start}] (Distance 0)")
while queue:
next_layer: list[int] = []
for _ in range(len(queue)): #Processing all nodes in the current layer
node = queue.popleft()
for nxt in graph[node]:
if dist[nxt] == -1:
dist[nxt] = dist[node] + 1
queue.append(nxt)
next_layer.append(nxt)
if next_layer:
layer += 1
print(f"Layer {layer}: {next_layer} (Distance {layer})")
#── BFS vs DFS Comparison ──────────────────────────────────────────────────────
def dfs_order(
graph: list[list[int]],
start: int,
n: int,
) -> list[int]:
"""DFS Visit Order (for Comparison)."""
visited = [False] * (n + 1)
order: list[int] = []
def _dfs(node: int) -> None:
visited[node] = True
order.append(node)
for nxt in graph[node]:
if not visited[nxt]:
_dfs(nxt)
_dfs(start)
return order
#── Main ─────────────────────────────────────────────────────────────────────────
if __name__ == "__main__":
#Tree-structured graph
# 1
# /|\
# 2 3 4
# /| |
# 5 6 7
n = 7
edges = [(1, 2), (1, 3), (1, 4), (2, 5), (2, 6), (4, 7)]
graph: list[list[int]] = [[] for _ in range(n + 1)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
print("=" * 55)
print("BFS vs DFS visit order comparison")
print("=" * 55)
bfs_order, dist = bfs(graph, 1, n)
dfs_ord = dfs_order(graph, 1, n)
print(f"BFS order: {bfs_order}")
print(f"DFS order: {dfs_ord}")
print(f"Shortest distance: {dist[1:]}")
print("\n=== BFS Layer-by-Layer Traversal ===")
bfs_verbose(graph, 1, n)
#Linear graph
print("\n=== Linear Graph 1─2─3─4─5 ===")
n2 = 5
g2: list[list[int]] = [[] for _ in range(n2 + 1)]
for i in range(1, n2):
g2[i].append(i + 1)
g2[i + 1].append(i)
bfs_ord2, dist2 = bfs(g2, 1, n2)
print(f"BFS order: {bfs_ord2}")
print(f"Distance array: {dist2[1:]}")
#Disconnected Graph
print("\n=== Disconnected Graph ===")
#1─2 3─4 5(Isolated)
n3 = 5
g3: list[list[int]] = [[] for _ in range(n3 + 1)]
for u, v in [(1, 2), (3, 4)]:
g3[u].append(v)
g3[v].append(u)
_, dist3 = bfs(g3, 1, n3)
print(f"Start=1 Distance: {dist3[1:]}")
print("-1 = unreachable")
#Distance-based layer output
print("\n=== Nodes by Distance ===")
for d in range(max(x for x in dist if x >= 0) + 1):
nodes = [i for i in range(1, n + 1) if dist[i] == d]
print(f"Distance {d}: {nodes}")
src/02_bfs_shortest_path.pyPython
"""Topic : BFS Shortest Path — dist Array, Path Reconstruction
Time : O(V + E)
Space : O(V)"""
from collections import deque
#── Shortest Path Distance ────────────────────────────────────────────────────────────
def bfs_dist(
graph: list[list[int]],
start: int,
n: int,
) -> list[int]:
"""Calculate the shortest distance to all nodes using BFS.
Returns:
dist[i] = shortest distance from start to i (-1 = unreachable)"""
dist = [-1] * (n + 1)
dist[start] = 0
queue: deque[int] = deque([start])
while queue:
node = queue.popleft()
for nxt in graph[node]:
if dist[nxt] == -1:
dist[nxt] = dist[node] + 1
queue.append(nxt)
return dist
#── Path Reconstruction ───────────────────────────────────────────────────────────────
def bfs_with_parent(
graph: list[list[int]],
start: int,
n: int,
) -> tuple[list[int], list[int]]:
"""Path reconstruction with BFS + parent array.
Returns:
(dist, parent)
parent[i] = parent of i in BFS tree (-1 if none)"""
dist = [-1] * (n + 1)
parent = [-1] * (n + 1)
dist[start] = 0
queue: deque[int] = deque([start])
while queue:
node = queue.popleft()
for nxt in graph[node]:
if dist[nxt] == -1:
dist[nxt] = dist[node] + 1
parent[nxt] = node
queue.append(nxt)
return dist, parent
def reconstruct_path(parent: list[int], start: int, end: int) -> list[int]:
"""Reconstruct the path from start → end using the parent array.
Returns:
path list (empty list if unreachable)"""
if parent[end] == -1 and end != start:
return [] #Unreachable
path: list[int] = []
node = end
while node != -1:
path.append(node)
node = parent[node]
return path[::-1]
#── Shortest Distance to Specific Target ───────────────────────────────────────────────
def bfs_to_target(
graph: list[list[int]],
start: int,
target: int,
n: int,
) -> int:
"""Shortest distance from start to target (early exit).
Returns:
shortest distance (-1 if unreachable)"""
if start == target:
return 0
dist = [-1] * (n + 1)
dist[start] = 0
queue: deque[int] = deque([start])
while queue:
node = queue.popleft()
for nxt in graph[node]:
if dist[nxt] == -1:
dist[nxt] = dist[node] + 1
if nxt == target:
return dist[nxt]
queue.append(nxt)
return -1
#── Main ─────────────────────────────────────────────────────────────────────────
if __name__ == "__main__":
#Graph Construction
# 1─2─3─6
# │ │
# 4─5
n = 6
edges = [(1, 2), (1, 4), (2, 3), (2, 5), (3, 6), (4, 5)]
graph: list[list[int]] = [[] for _ in range(n + 1)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
print("=" * 55)
print("BFS Shortest Path")
print("=" * 55)
start = 1
dist, parent = bfs_with_parent(graph, start, n)
print(f"Start Point: {start}")
print(f"Distance Array: {dist[1:]}")
for target in [1, 3, 5, 6]:
path = reconstruct_path(parent, start, target)
d = dist[target]
print(f"{start} → {target}: Distance={d}, Path={path}")
#Disconnected Node
n2 = 5
g2: list[list[int]] = [[] for _ in range(n2 + 1)]
for u, v in [(1, 2), (3, 4)]:
g2[u].append(v)
g2[v].append(u)
d2, p2 = bfs_with_parent(g2, 1, n2)
path_to_3 = reconstruct_path(p2, 1, 3)
print(f"Disconnected: 1 → 3 Path = {path_to_3} (Empty List = Unreachable)")
#Early Termination Test
print("=== Early Termination Shortest Distance ===")
for src, dst in [(1, 6), (1, 5), (4, 6)]:
d_fast = bfs_to_target(graph, src, dst, n)
d_full = bfs_dist(graph, src, n)[dst]
assert d_fast == d_full
print(f" {src} → {dst}: {d_fast}")
print("Accuracy Verification: PASS")
src/03_bfs_grid.pyPython
"""Topic : Grid BFS — Maze Shortest Path, 4 Directions
Time : O(R × C)
Space : O(R × C)"""
from collections import deque
DR = [-1, 1, 0, 0]
DC = [0, 0, -1, 1]
#── Grid BFS ─────────────────────────────────────────────────────────────────
def bfs_grid(
grid: list[list[int]],
sr: int, sc: int,
er: int, ec: int,
) -> int:
"""Shortest distance in a grid from (sr,sc) → (er,ec).
grid: 0=passable, 1=wall
Returns:
Shortest distance (-1 if unreachable)"""
rows = len(grid)
cols = len(grid[0])
if grid[sr][sc] == 1 or grid[er][ec] == 1:
return -1
dist = [[-1] * cols for _ in range(rows)]
dist[sr][sc] = 0
queue: deque[tuple[int, int]] = deque([(sr, sc)])
while queue:
r, c = queue.popleft()
if r == er and c == ec:
return dist[r][c]
for i in range(4):
nr, nc = r + DR[i], c + DC[i]
if (0 <= nr < rows and 0 <= nc < cols
and dist[nr][nc] == -1
and grid[nr][nc] == 0):
dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))
return -1
def bfs_grid_with_path(
grid: list[list[int]],
sr: int, sc: int,
er: int, ec: int,
) -> tuple[int, list[tuple[int, int]]]:
"""Grid BFS + path reconstruction.
Returns:
(Shortest distance, list of path coordinates)"""
rows = len(grid)
cols = len(grid[0])
dist = [[-1] * cols for _ in range(rows)]
parent: list[list[tuple[int, int] | None]] = [
[None] * cols for _ in range(rows)
]
dist[sr][sc] = 0
queue: deque[tuple[int, int]] = deque([(sr, sc)])
while queue:
r, c = queue.popleft()
for i in range(4):
nr, nc = r + DR[i], c + DC[i]
if (0 <= nr < rows and 0 <= nc < cols
and dist[nr][nc] == -1
and grid[nr][nc] == 0):
dist[nr][nc] = dist[r][c] + 1
parent[nr][nc] = (r, c)
queue.append((nr, nc))
if dist[er][ec] == -1:
return -1, []
#Path backtracking
path: list[tuple[int, int]] = []
cur: tuple[int, int] | None = (er, ec)
while cur is not None:
path.append(cur)
r, c = cur
cur = parent[r][c]
return dist[er][ec], path[::-1]
#── Visualization ──────────────────────────────────────────────────────────────
def print_grid_with_path(
grid: list[list[int]],
path: list[tuple[int, int]],
sr: int, sc: int,
er: int, ec: int,
) -> None:
"""Print grid showing path."""
path_set = set(path)
rows = len(grid)
cols = len(grid[0])
print()
for r in range(rows):
row_str = ""
for c in range(cols):
if (r, c) == (sr, sc):
row_str += "S"
elif (r, c) == (er, ec):
row_str += "E"
elif (r, c) in path_set:
row_str += "*"
elif grid[r][c] == 1:
row_str += "█"
else:
row_str += "."
print(" " + row_str)
#── Main ─────────────────────────────────────────────────────────────────────
if __name__ == "__main__":
#Baekjoon 2178 style maze
maze = [
[0, 0, 1, 0, 0, 0],
[0, 0, 1, 0, 1, 0],
[1, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 0],
]
sr, sc = 0, 0
er, ec = len(maze) - 1, len(maze[0]) - 1
print("=" * 50)
print("Grid BFS maze exploration")
print("=" * 50)
print("Maze (█=wall, .=path):")
for row in maze:
print(" " + "".join("█" if c else "." for c in row))
dist, path = bfs_grid_with_path(maze, sr, sc, er, ec)
print(f"Shortest distance: {dist}")
print(f"Path coordinates: {path}")
print("Path visualization (S=Start, E=End, *=Path):")
print_grid_with_path(maze, path, sr, sc, er, ec)
#Grid without walls — Shortest distance = Manhattan distance
open_grid = [[0] * 5 for _ in range(5)]
d = bfs_grid(open_grid, 0, 0, 4, 4)
print(f"5×5 open grid (0,0)→(4,4): {d} (Manhattan: {4+4})")
#If blocked
blocked = [[0, 1], [1, 0]]
d_blocked = bfs_grid(blocked, 0, 0, 1, 1)
print(f"Blocked grid: {d_blocked} (-1 if impossible)")
#Verify accuracy
assert dist == 8 or dist >= 0 #May vary depending on the maze
assert bfs_grid(open_grid, 0, 0, 4, 4) == 8
print("Accuracy check: PASS")
src/04_bfs_multi_source.pyPython
"""Topic : Multi-Source BFS — Simultaneous search from multiple starting points
Time : O(V + E) or O(R × C)
Space : O(V)"""
from collections import deque
DR = [-1, 1, 0, 0]
DC = [0, 0, -1, 1]
#── Multiple Starting Points BFS (Graph) ─────────────────────────────────────────────────
def multi_source_bfs(
graph: list[list[int]],
sources: list[int],
n: int,
) -> list[int]:
"""Perform BFS simultaneously from multiple starting points.
Returns the distance to each node from the nearest starting point."""
dist = [-1] * (n + 1)
queue: deque[int] = deque()
#Insert all starting points into the initial queue
for src in sources:
dist[src] = 0
queue.append(src)
while queue:
node = queue.popleft()
for nxt in graph[node]:
if dist[nxt] == -1:
dist[nxt] = dist[node] + 1
queue.append(nxt)
return dist
#── Tomato Problem Style (Baekjoon 7576) ──────────────────────────────────────────
def tomato_ripening(grid: list[list[int]]) -> int:
"""Ripen adjacent tomatoes from already ripe tomatoes (1) in one day.
The minimum number of days required for all tomatoes to ripen.
0 = unripe tomato, 1 = ripe tomato, -1 = empty cell
Returns:
Minimum number of days (-1 if impossible)"""
rows = len(grid)
cols = len(grid[0])
dist = [[-1] * cols for _ in range(rows)]
queue: deque[tuple[int, int]] = deque()
#Insert all ripe tomatoes into the queue
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
dist[r][c] = 0
queue.append((r, c))
while queue:
r, c = queue.popleft()
for i in range(4):
nr, nc = r + DR[i], c + DC[i]
if (0 <= nr < rows and 0 <= nc < cols
and grid[nr][nc] == 0
and dist[nr][nc] == -1):
dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))
#If any unripe tomatoes remain, -1
max_days = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 0 and dist[r][c] == -1:
return -1
if dist[r][c] != -1:
max_days = max(max_days, dist[r][c])
return max_days
#── Multiple Starting Points BFS — Color by the Nearest Starting Point ────────────────────────────────
def color_by_nearest_source(
grid: list[list[int]],
sources: list[tuple[int, int]],
) -> list[list[int]]:
"""Paint each empty cell with the color of the nearest starting point.
Returns:
color array (number indicating which starting point each cell came from, -1 = unreachable)"""
rows = len(grid)
cols = len(grid[0])
color = [[-1] * cols for _ in range(rows)]
dist = [[float('inf')] * cols for _ in range(rows)]
queue: deque[tuple[int, int, int]] = deque() # (r, c, color_id)
for i, (r, c) in enumerate(sources):
color[r][c] = i
dist[r][c] = 0
queue.append((r, c, i))
while queue:
r, c, cid = queue.popleft()
for i in range(4):
nr, nc = r + DR[i], c + DC[i]
if (0 <= nr < rows and 0 <= nc < cols
and grid[nr][nc] == 0
and dist[nr][nc] == float('inf')):
dist[nr][nc] = dist[r][c] + 1
color[nr][nc] = cid
queue.append((nr, nc, cid))
return color
#── Visualization ──────────────────────────────────────────────────────────────
def print_grid(grid: list[list], title: str) -> None:
symbols = {0: ".", 1: "T", -1: "□", 2: "2"}
print(f"\n=== {title} ===")
for row in grid:
print(" " + " ".join(
str(c) if isinstance(c, int) and c >= 0 else ("□" if c == -1 else str(c))
for c in row
))
#── Main ─────────────────────────────────────────────────────────────────────
if __name__ == "__main__":
#Tomato problem simulation
tomato_grid = [
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1], #Bottom right
]
print("=" * 50)
print("Tomato problem (Multiple Starting Points BFS)")
print("=" * 50)
print_grid(tomato_grid, "Initial state (T = ripe tomato)")
days = tomato_ripening([row[:] for row in tomato_grid])
print(f"Days required for all tomatoes to ripen: {days}")
#Multiple starting points
multi_tomato = [
[1, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, -1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1],
]
print_grid(multi_tomato, "Multiple starting point tomatoes (□ = empty space)")
days2 = tomato_ripening([row[:] for row in multi_tomato])
print(f"Days required for all tomatoes to ripen: {days2}")
#Impossible case
impossible = [
[1, 0, -1, 0, 0],
]
days3 = tomato_ripening(impossible)
print(f"Impossible case: {days3} (-1 if impossible)")
#Graph multiple starting points
print("\n=== Graph Multiple Starting Points BFS ===")
n = 7
edges = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7)]
g: list[list[int]] = [[] for _ in range(n + 1)]
for u, v in edges:
g[u].append(v)
g[v].append(u)
sources = [1, 7]
dist_multi = multi_source_bfs(g, sources, n)
print(f"Starting points {sources}, shortest distance: {dist_multi[1:]}")
print("← Distance from each node to the nearest starting point")
#Verify accuracy
assert tomato_ripening([[1, 0, 0], [0, 0, 0]]) == 4
print("Accuracy check: PASS")
Assignment
Apply BFS shortest path and multiple starting points to practical problems.
Problem 1: Baekjoon 1260 – DFS and BFS (Silver II)
Same problem as the previous assignment (Lesson 13).
This time, focus on the BFS part.
Approach
from collections import deque
queue = deque([start])
visited[start] = True
while queue:
node = queue.popleft()
print(node)
for nxt in sorted(graph[node]):
if not visited[nxt]:
visited[nxt] = True
queue.append(nxt)
Problem 2: Baekjoon 2178 – Maze Exploration (Silver I)
Problem Description
Shortest distance in an NxM maze from (1,1) → (N,M) (number of moves).
'1' = passable, '0' = wall.
Input format
4 6
101111
101010
111010
000110
Approach
BFS for shortest distance from (0,0) → (N-1,M-1)
dist[0][0] = 1 (including starting point)
Notes
Start counting distance from 1 (including starting point)
String input → check if each character is '1'
Problem 3: Baekjoon 7576 – Tomato (Gold V)
Problem Description
In an MxN box, ripe tomatoes (1) ripen adjacent tomatoes in one day.
Print the minimum number of days for all tomatoes to ripen.
If impossible, print -1.
Approach
Multi-start BFS:
queue = deque()
for r in range(n):
for c in range(m):
if grid[r][c] == 1:
queue.append((r, c))
dist[r][c] = 0
2178: Initial value of dist 1 (including starting point)?
2178: Is range check correct?
7576: Did you put all multiple starting points into the queue?
7576: Handle so that empty cells (-1) cannot be passed?
7576: Print 0 if all are ripe from the start?
Model Answer
Refer to the reference solution below.
Show the reference solution
Try the assignment yourself first — comparing your attempt with a working solution is where most of the learning happens.
boj_1260.pyPython
"""Baekjoon 1260 – DFS and BFS
https://www.acmicpc.net/problem/1260
Time : O((V + E) log V)
Space : O(V + E)"""
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
def main() -> None:
n, m, v = map(int, input().split())
graph: list[list[int]] = [[] for _ in range(n + 1)]
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
for i in range(1, n + 1):
graph[i].sort()
# DFS
visited_dfs = [False] * (n + 1)
dfs_result: list[int] = []
def dfs(node: int) -> None:
visited_dfs[node] = True
dfs_result.append(node)
for nxt in graph[node]:
if not visited_dfs[nxt]:
dfs(nxt)
dfs(v)
print(' '.join(map(str, dfs_result)))
# BFS
visited_bfs = [False] * (n + 1)
queue: deque[int] = deque([v])
visited_bfs[v] = True
bfs_result: list[int] = []
while queue:
node = queue.popleft()
bfs_result.append(node)
for nxt in graph[node]:
if not visited_bfs[nxt]:
visited_bfs[nxt] = True
queue.append(nxt)
print(' '.join(map(str, bfs_result)))
if __name__ == "__main__":
main()
boj_2178.pyPython
"""Baekjoon 2178 – Maze Exploration
https://www.acmicpc.net/problem/2178
Time : O(N × M)
Space : O(N × M)
Strategy: BFS shortest path (count the number of moves including the starting point)"""
import sys
from collections import deque
input = sys.stdin.readline
DR = [-1, 1, 0, 0]
DC = [0, 0, -1, 1]
def main() -> None:
n, m = map(int, input().split())
maze = [list(map(int, list(input().rstrip()))) for _ in range(n)]
dist = [[-1] * m for _ in range(n)]
dist[0][0] = 1 #Including the starting point
queue: deque[tuple[int, int]] = deque([(0, 0)])
while queue:
r, c = queue.popleft()
if r == n - 1 and c == m - 1:
break
for i in range(4):
nr, nc = r + DR[i], c + DC[i]
if 0 <= nr < n and 0 <= nc < m and maze[nr][nc] == 1 and dist[nr][nc] == -1:
dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))
print(dist[n - 1][m - 1])
if __name__ == "__main__":
main()
boj_7576.pyPython
"""Baekjoon 7576 – Tomato
https://www.acmicpc.net/problem/7576
Time : O(M × N)
Space : O(M × N)
Strategy: Multi-source BFS — start simultaneously from all ripe tomatoes"""
import sys
from collections import deque
input = sys.stdin.readline
DR = [-1, 1, 0, 0]
DC = [0, 0, -1, 1]
def main() -> None:
m, n = map(int, input().split()) #m=number of columns, n=number of rows
grid = [list(map(int, input().split())) for _ in range(n)]
dist = [[-1] * m for _ in range(n)]
queue: deque[tuple[int, int]] = deque()
#Insert all ripe tomatoes into the queue
for r in range(n):
for c in range(m):
if grid[r][c] == 1:
dist[r][c] = 0
queue.append((r, c))
while queue:
r, c = queue.popleft()
for i in range(4):
nr, nc = r + DR[i], c + DC[i]
if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] == 0 and dist[nr][nc] == -1:
dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))
#Calculate results
ans = 0
for r in range(n):
for c in range(m):
if grid[r][c] == 0 and dist[r][c] == -1:
print(-1)
return
if dist[r][c] != -1:
ans = max(ans, dist[r][c])
print(ans)
if __name__ == "__main__":
main()
Learn this lesson with a mentor
Work through the Python Algorithms & Data Structures track on your own, or join a guided cohort at our Pitampura campus and online.