from collections import deque
dx = [0,0,-1,1]
dy = [1,-1,0,0]
def BFS(x, y, maps):
queue = deque()
queue.append((x,y))
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if 0<= nx<len(maps) and 0<=ny<len(maps[0]) and maps[nx][ny] == 1:
maps[nx][ny] = maps[x][y] + 1
queue.append((nx,ny))
def solution(maps):
BFS(0, 0, maps)
if maps[-1][-1] == 1:
return -1
else:
return maps[-1][-1]
BFS를 활용하여 최단거리 문제를 해결할 수 있다.