[Python/파이썬] - 백준(BOJ) 2178번 : 미로 탐색

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

2178번: 미로 탐색

 

간단한 BFS 문제

시작 점의 좌표를 큐에 저장한 뒤 주변 좌표를 탐색한다.

이때 조건은 좌표가 N, M을 벗어나지 않는지 && 이동할 수 있는 칸인지 && 방문한 적 없는지

이 세가지만 확인하면 된다.

세 조건을 충족한다면 큐에 넣고 visit을 1로 변경해준다

반복이 종료된다면 N, M번째 좌표를 출력해주자

 

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

n, m = map(int,input().split())
arr = [list(map(int,input().strip())) for _ in range(n)]
visit = [[0 for _ in range(m)] for _ in range(n)]
dy = [0,-1,0,1]
dx = [1,0,-1,0]
queue = deque([[0,0]])
visit[0][0] = 1
while queue:
    y, x = queue.popleft()
    for i in range(4):
        yy = y + dy[i]
        xx = x + dx[i]
        if 0 <= yy < n and 0 <= xx < m and arr[yy][xx] == 1 and visit[yy][xx] == 0:
            visit[yy][xx] = visit[y][x] + 1
            queue.append([yy,xx])
print(visit[n-1][m-1])