[BOJ] 2178 / 미로 탐색 / Python 파이썬

[BOJ] 2178 / 미로 탐색 / Python 파이썬

[BOJ] 2178 / 미로 탐색 / Python 파이썬

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

2178번: 미로 탐색

 

풀이

경로탐색의 기본 문제이다.

 

bfs 로 경로상의 이동 거리를 저장하며 경로를 진행하도록 하였다.

 

from collections import deque

N, M = map(int, input().split())

maps = []

for _ in range(N):
    maps.append(list(map(int, list(input()))))

dq = deque()
dq.append((0, 0))

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

while dq:
    y, x = dq.popleft()

    for i in range(4):
        Y = y + dy[i]
        X = x + dx[i]

        if 0 <= Y < N and 0 <= X < M and maps[Y][X]:
            if maps[Y][X] == 1:
                maps[Y][X] = maps[y][x] + 1
                dq.append((Y, X))
            elif maps[Y][X] > maps[y][x] + 1:
                maps[Y][X] = maps[y][x] + 1
                dq.append((Y, X))

print(maps[N-1][M-1])