블록 이동하기
로봇개발자 "무지"는 한달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있다. 준비 중인 로봇은 2*1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N*N 크기의 지도에서 2*1 크기인 로봇을 움직여 (N,N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 한다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1,1)로 하며 지도 내에 표시된 숫자 "0"은 빈칸을 "1"은 벽을 나타낸다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없다. 로봇은 처음에 아래 그림과 같이 좌표 (1,1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있다.
로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이동한다. 예를 들어, 위 그림에서 오른쪽으로 한 칸 이동한다면 (1,2),(2,3) 두 칸을 차지하게 되며, 아래로 이동한다면 (2,1)(2,2) 두 칸을 차지하게 된다. 로봇이 차지하는 두 칸 중 어느 한 칸이라도 (N,N) 위치에 도착하면 된다.
로봇은 다음과 같이 조건에 따라 회전이 가능하다.
위 그림과 같이 로봇은 90도씩 회전할 수 있다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 한다. 로봇이 한 칸 이동하거나 90도 회전하는데 걸리는 시간은 정확히 1초이다.
"0"과 "1"로 이루어진 지도에 board가 주어질 때, 로봇이 (N,N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성하라.
제한 사항
- board의 한 변의 길이는 5 이상 100이하이다.
- board의 원소는 0 또는 1이다.
- 로봇이 처음에 놓여 있는 칸 (1,1),(1,2)는 항상 0으로 주어진다.
- 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어진다.
