12. DFS/BFS : 미로 탈출

N*M의 미로 탈출

 

input:

n * m (미로의 크기)

0101.. <--- 미로의 구성

0020..

..

 

rule:

나의 위치 (1,1).

한번에 한 칸씩 움직일 수 있음.

0은 괴물, 1은 길.

최단거리룰 구하라.

칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산.

 

최단 거리를 구하는 문제는 bfs를 사용??

 

from collections import deque
n, m = map(int,input().split())
x, y = 0, 0

graph = []

steps=[(-1,0),(1,0),(0,-1),(0,1)]

for i in range(n):
  graph.append(list(map(int,input())))

def bfs(x,y):
  queue = deque()
  queue.append((x,y))
  
  while queue :
    x, y = queue.popleft()
    for step in steps:
      nx = x+ step[0]
      ny = y+ step[1]

      if nx < 0 or nx >= n or ny < 0 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))

아직 queue를 구현하는데 많이 어색한 것 같다 ㅠㅠ 엄청 해맸다.

que의 개념을 확실히 잡자.