[백준] 2178 미로 탐색

# bfs : 최단거리 보장
# bfs : "바로 보드에 저장해버리자 (이동 시 1씩 증가) -> 거기까지 가는데 걸리는 값 개념으로 접근!"

 

# 문제 풀이 
from collections import deque

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

# 출력 : 지나야하는 최소 칸 수
mymap = []
for i in range(n):
	mymap.append(list(map(int,list(input())))) # 여기서 약간 err (int -> str)


print(mymap[0][0],type(mymap[0][0]) , "<< ")

xb = [0,1,0,-1]
yb = [1,0,-1,0]

visited = [[False] * m for _ in range(n)]


tmpmap = [k[:] for k in mymap]

q = deque([(0,0)])
visited[0][0] = True

while q:
	a = q.popleft()
	for j in range(4):
		x = a[0] + xb[j]
		y = a[1] + yb[j]
		if x >= n or x < 0 or y >= m or y < 0:
			continue
		if (x == (n-1)) and (y == (m-1)):
			pass

		if (tmpmap[x][y] == 1) and (visited[x][y] != True):
			q.append((x,y))
			visited[x][y] = True
			# edit
			tmpmap[x][y] = tmpmap[a[0]][a[1]] + 1

print(tmpmap[n-1][m-1])