[백준] 2178번 미로 탐색

[백준] 2178번 미로 탐색 - 파이썬

코딩 코딩 코오딩 2021. 8. 18. 20:50

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

2178번: 미로 탐색

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

www.acmicpc.net

from collections import deque
n, m = map(int, input().split())
walk = 0
def bfs(x,y):
    
    queue = deque()
    queue.append((x,y))

    dx = [-1,1,0,0]
    dy = [0,0,-1,1]


    while queue:
        x,y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >=0 and ny >=0 and ny < m and nx <n:
                if graph[nx][ny] == 1:
                    graph[nx][ny] = graph[x][y]+1
                    queue.append((nx,ny))

    return graph[n-1][m-1]                    


graph = []

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

print(bfs(0,0))