ラビリンス脱出[bfs]
# 1. 처음 위치는 (1,1) / 미로의 출구는 (n,m)
# 2. 괴물 있는 부분은 0/ 없는 부분은 1
# 3. 탈출하기 위해 움직일 최소 칸의 개수 구하기
# 아이디어 : dfs or bfs -> bfs 같음
from collections import deque
n,m=map(int,input().split())
graph=[]
for i in range(n):
graph.append(list(map(int,input())))
# 이동할 네 방향 설정
dx=[-1,1,0,0]
dy=[0,0,-1,1]
# bfs 소스 코드 구현
def bfs(x,y):
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 nx<0 or ny<0 or nx>=n or ny>=m:
continue
if graph[nx][ny]==0:
continue
if graph[nx][ny]==1:
graph[nx][ny]=graph[x][y]+1
queue.append((nx,ny))
return graph[n-1][m-1]
print(bfs(0,0))
Reference
この問題について(ラビリンス脱出[bfs]), 我々は、より多くの情報をここで見つけました https://velog.io/@csy9604/미로탈출-bfsテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol