[파이썬] BOJ_2178(미로 탐색)

문제

 

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

2178번: 미로 탐색

---

 

해설

 

지도 내에서 칸이 1이면 이동한다.

이동을 하면 그 전 칸의 이동한 값에 +1을 해준다.

---

코드

 

-파이썬

#백준 2178(미로 탐색)

import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append([*map(int, str(input().rstrip()))])

def bfs(a, b):
    #상/하/좌/우
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    Q = deque([(a, b)])
    while Q:
        a, b = Q.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            #범위 내, 칸이 1이어야 이동 가능
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
                graph[nx][ny] = graph[a][b] + 1
                Q.append((nx, ny))

    return graph[n-1][m-1]
print(bfs(0, 0))