미로 찾기 2

문제 설명

가로와 세로의 길이가 n이고 통로(0) 또는 벽(1)으로만 이루어진 $n \times n$ 미로 정보 maze가 매개 변수로 주어질 때 (1, 1)에서 출발해 (n, n)에 도착하기까지 최소 이동 횟수를 반환하는 solution 함수를 작성하시오.

주어진 미로 정보 maze 밖으로는 나갈 수 없다고 가정합니다. 주어진 미로 정보 maze는 항상 (1, 1)에서 출발해 (n, n)에 도착할 수 있다고 가정합니다.

제한 사항

• maze는 $n \times n$ 정사각 형태로 주어지며 가로 및 세로 길이는 3 이상 1,000 이하의 자연수입니다.
• maze의 모든 원소는 0(통로) 또는 1(벽)로만 이루어져 있습니다.
  • 0(통로)은 미로에서 지나다닐 수 있고, 1(벽)은 미로에서 지나다닐 수 없습니다.
  • 첫 번째 행, 첫 번째 열의 원소 (1, 1)과 n번째 행, n번째 열의 원소 (n, n)는 항상 0으로 주어집니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• (1,1)에서 출발해 (3,3)에 도착하기까지 최단 경로는 다음과 같으며 총 4번의 이동이 필요합니다.
  • (1,1) $\rightarrow$ (1,2) $\rightarrow$ (2,2) $\rightarrow$ (3,2) $\rightarrow$ (3,3)

2번 테스트케이스 설명

• (1,1)에서 출발해 (4,4)에 도착하기까지 최단 경로는 다음과 같으며 총 6번의 이동이 필요합니다.
  • (1,1) $\rightarrow$ (1,2) $\rightarrow$ (2,2) $\rightarrow$ (3,2) $\rightarrow$ (3,3) $\rightarrow$ (3,4) $\rightarrow$ (4,4)

3번 테스트케이스 설명

• (1,1)에서 출발해 (5,5)에 도착하기까지 최단 경로는 다음과 같으며 총 16번의 이동이 필요합니다.
  • (1,1) $\rightarrow$ (1,2) $\rightarrow$ (1,3) $\rightarrow$ (1,4) $\rightarrow$ (1,5) $\rightarrow$ (2,5) $\rightarrow$ (3,5) $\rightarrow$ (3,4) $\rightarrow$ (3,3) $\rightarrow$ (3,2) $\rightarrow$ (3,1) $\rightarrow$ (4,1) $\rightarrow$ (5,1) $\rightarrow$ (5,2) $\rightarrow$ (5,3) $\rightarrow$ (5,4) $\rightarrow$ (5,5)