[백준] 2178 | 미로 탐색 [파이썬/python]

문제

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

미로가 주어질 때, (1, 1)에서 출발해서 (N, M)에 도달할 때까지 거치는 칸의 최솟값을 구하는 문제이다.

1로는 이동할 수 있고, 0으로는 이동할 수 없다.

 

접근

문제에서는 미로를 N*M 사이즈 배열로 표현하고 있는데, (1, 1)부터 (N, M)까지의 좌표가 존재한다. 0이 아닌 1부터 시작함에 유의해야 한다.

(1, 1)에서 출발해, 이동 가능한 곳만 골라 미로를 순회해 답을 구했다. BFS를 활용했다.

 

코드

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

N, M = map(int, input().split())
maps = [list(map(int, input().strip())) for __ in range(N)]
        
d = ((-1, 0), (1, 0), (0, -1), (0, 1))
q = deque([(0, 0, 1)])

while q:
    x, y, cnt = q.popleft()
    if x == N-1 and y == M-1:
        print(cnt)
    for dx, dy in d:
        xx = x + dx
        yy = y + dy
        if 0 <= xx < N and 0 <= yy < M and maps[xx][yy]:
            maps[xx][yy] = 0
            q.append((xx, yy, cnt + 1))
    cnt += 1