미로탐색
- N*M 크기의 배열로 표현되는 미로가 있다.
-
(1,1)에서 출발하여 (N,M)의 위치로 이동할 때, 지나야하는 최소 칸 수 구하기
- 항상 체크하자
- 배열의 범위를 넘었는지
- 갈 수 있는 곳인지
- 이미 방문한 곳인지
def isSafe(x, y):
return 0 <= x < N and 0 <= y < M and arr[x][y] != 0
# 0은 이동할 수 없는 칸, 1은 이동 가능한 칸
N, M = map(int, input().split())
arr = [list(map(int, input())) for _ in range(N)]
# 상하좌우
dy = [1, -1, 0, 0]
dx = [0, 0, -1, 1]
visited = [[0]*M for _ in range(N)]
q = [(0, 0)]
visited[0][0] = 1 # 시작 위치를 체크 (나중에 시작점으로 다시 되돌아오는 경우 방지)
while q:
x, y = q.pop(0)
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if isSafe(nx, ny) and not visited[nx][ny]:
# if 0 <= nx < N and 0 <= ny < M and arr[nx][ny] and not visited[nx][ny]:
visited[nx][ny] = visited[x][y]+1
q.append((nx, ny))
print(visited[N-1][M-1])