[백준,PS,BFS][PYTHON] #2178 . 미로탐색

https://www.acmicpc.net/problem/2178

from collections import deque

def bfs(n,m,maps):
   
    dx = [1,-1,0,0] #이동하기위한 x 좌표 후보
    dy = [0,0,1,-1] #이동하기위한 y 좌표 후보
    
    while q: # 큐안에 원소가 계속 존재하는 동안 
        
        for _ in range(len(q)):#큐의 개수만큼도는데
            x,y = q.popleft()#큐에서 한개를 뽑아서
          
            
            for i in range(4): # 동서남북후보군을 정해준다.
                nx = x + dx[i]
                ny = y + dy[i]
                
                if 0<=nx<n and 0<=ny<m: #다음좌표가 n,m을 넘지않고
                    
                    if visited[nx][ny] == 0 and maps[nx][ny] ==1:#방문하지않고 1이라면
                        
                        q.append([nx,ny]) #큐에 넣어주고
                        visited[nx][ny] =1 #방문함으로 바꿔주고
                        final_map[nx][ny] = final_map[x][y] +1 #경로의 수를 나타내주는 맵
                    
###################main#############################                        
n,m = map(int, input().split())
maps = []
visited = [[0] *m for _ in range(n)]
final_map =[[0] *m for _ in range(n)]

q = deque()
count =0

for i in range(n):
    value = list(map(int,list(input()))) # 111111 붙어있는 수를 입력받는 방법
    maps.append(value)
    
q.append([0,0]) #무조건 0,0에서 시작하니까 0,0부터 넣어주는것        
visited[0][0] =1 #넣어준 시작값은 무조건 방문이니까 1

bfs(n,m,maps) #bfs 시작

#for i in final_map:
#    print(i , sep = '\n')
print(final_map[n-1][m-1] + 1) #맵의 마지막값이 0,0 ->n,m까지의 경로이동횟수