python - BFS - problem solving example

강의: https://youtu.be/7C9RgOcvkvo

코드:

# BFS example
from collections import deque

# 1. input
n, m = map(int, input.split())

graph=[]
for i in range(n):
    graph[i].append(list(map(int, input())))
    
# 2. find shortest path
# top, bottom, left, right
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

def bfs(r,c):
    queue = deque()
    queue.append(r,c)
    while queue:
        r,c = queue.popleft()
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            #check out of boundary
            if nr<0 or nr>=n or nc<0 or nc>=m :
                continue
            #check wall
            if graph[nr][nc]==0:
                continue
            #write the shortest path
            if graph[nr][nc] == 1: # **check if haven't visited
                graph[nr][nc] = graph[r][c]+1
                queue.append((nr, nc))
    return graph[n-1][m-1]
    

# 3. print result
print(bfs(0,0))

Time Complexity :
O(V+E)
V is the number of nodes in the graph,
E is the number of edges