미로탐색
방법을 모르겠을때는 그냥 외우자. 외우는게 짱일때가 많다.
def bfs():
arr = []
arr.append([0, 0])
visit[0][0] = 1
while arr:
cur = arr.pop(0) # [0,0]
x = cur[0] # 0
y = cur[1] # 0
if cur == [row-1, col-1]:
print(visit[x][y])
break
now = visit[x][y] # now = 0
for i in range(len(dir)): # dir의 각 요소
wx = x + dir[i][0]
wy = y + dir[i][1]
# 4보다 크거나 같거나,
# 6보다 크거나 같거나
# 0 보다 작으면 건너뜀
# 처음경우 i가 2,3일때 건너뜀
# 0일 때는 y가 1늘고
# 1일때는 x가 1늘음
if wx >= row or wy >= col or wx < 0 or wy < 0:
continue
# 방문한 적이 없고
# 맵에서 값이 1이면
# 방문한자리에 똥은 왜남기고...? 그냥 True/False하는...게 아니라
# bfs니깐 다시 돌아가야해서 남기는구나..
if visit[wx][wy] == 0 and map[wx][wy] == '1':
visit[wx][wy] = now + 1
print(wx,wy,visit[wx][wy])
arr.append([wx, wy])
row, col = map(int, input().split())
map = [""] * row
visit = [[0] * col for _ in range(row)]
dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]
for i in range(row):
map[i] = input()
bfs()