백준. 2178번. 미로탐색 파이썬 풀이

백준. 2178번. 미로탐색 파이썬 풀이

문제링크 https://www.acmicpc.net/problem/2178

bfs를 사용하여 해결

import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10**6)

from collections import deque

# 세로 n 가로 m
n, m = map(int, input().split())

graph = []

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

# 이동방향: 위쪽, 아래쪽, 오른쪽, 왼쪽
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]


def bfs(graph, y, x):
    queue = deque()
    queue.append([y, x])

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

bfs(graph, 0, 0)

print(graph[-1][-1])