문제

N×M크기의 배열로 표현되는 미로가 있다.

1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

4 6
101111
101010
101011
111011

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

15

코드

• 상하좌우가 모두 연결되어있는 그래프로 나타낼 수 있음.
• 최단거리이므로 dfs 가 아닌 bfs 를 이용해야함.
• bfs 의 경우 queue 를 사용함 ( python 에선 deque 이용 )

from sys import stdin
from collections import deque

N, M = map(int, stdin.readline().split())
# matrix 배열
matrix = [list(map(int,stdin.readline().rstrip())) for _ in range(N)]

que = deque() # 큐
visited = [[0]*M for _ in range(N)] # 방문표시할 이차원배열

# 0,0 부터 시작하므로 ,큐와 방문배열에 표시하고 시작한다.
que.append([0,0])
visited[0][0]=1

# 상 하 좌 우 
dx = [-1,1,0,0]
dy = [0,0,-1,1]


def bfs(x,y):
	# 큐가 비기전까지 계속 돌면서
    while len(que)>0:
      x,y=que.popleft()
      # 상, 하 , 좌, 우 확인
      for i in range(len(dx)):
        nx = x+dx[i]
        ny = y+dy[i]
        if nx<0 or ny<0 or len(matrix)<=nx or len(matrix[0])<=ny: # matrix 밖으로 나가는 경우엔 계산 X
            continue
        if matrix[nx][ny]==1 and visited[nx][ny]==0: # 길인데 방문한적 없는 길이면
            matrix[nx][ny]= matrix[x][y]+1
            visited[nx][ny]=1
            que.append([nx,ny])

bfs(0,0)

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