백준 2178 (python): 미로 탐색

from collections import deque

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

# bfs로 풀고 도착하면 바로 break
# 갔던 곳 or 갈 수 없는 곳 가면 안됨 !

visited = [[0] * m for i in range(n)]
path = [[0, -1], [0, 1], [-1, 0], [1, 0]] # 갈수 있는 경로
graph = []

for _ in range(n):
    graph.append(list(map(int, input())))
    
def bfs(graph, start, visited):
    q = deque([start])
    visited[start[0]][start[1]] = 1
    
    while q:
        v = q.popleft()
        
        if v[0] == (n-1) and v[1] == (m-1): # 도착 위치라면 종료
            break
        
        for i in path: # 경로 확인
            new = [0, 0]
            new[0] = v[0] + i[0]
            new[1] = v[1] + i[1]
            
            # 해당 경로가 주어진 범위 내에 있어야 함
            if new[0] >= 0 and new[0] < n and new[1] >= 0 and new[1] < m:
                # 해당 경로는 방문한 적 없어야 함
                if visited[new[0]][new[1]] == 0:
                    # 해당 경로로 갈 수 있어야 함
                    if graph[new[0]][new[1]] == 1:
                        q.append(new)
                        visited[new[0]][new[1]] = visited[v[0]][v[1]] + 1
        
                
bfs(graph, [0, 0], visited)
print(visited[n-1][m-1])

 

bfs 로 풀기