BOJ 2178

Input

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다.

다음 N개의 줄에는 M개의 정수로 미로가 주어진다.

• 각각의 수들은 붙어서 입력으로 주어진다.

N, M = map(int, input().split())
miro = []
for _ in range(N):
  miro.append(list(int(s) for s in input()))

BFS

• 모든 경우의 수를 배열에 담아놓는다.

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

• 한 경우에 대해서가 아니라, 모든 경우의 수에 대해서 차례대로 확인 및 저장하므로

• BFS = 큐를 이용한다.

  queue = [[0,0]]
  
  while(queue):
    a, b = queue[0][0], queue[0][1]
    del queue[0]
    
    for i in range(4):
      y = a + dy[i]
      x = b + dx[i]
  
      if 0 <= y < N and 0 <= x < M and miro[y][x] == 1:
        miro[y][x] = miro[a][b] + 1
        queue.append([y,x])

Output

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다.

• 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

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