여행가의 등산

N×N 보드 판 형태로 산이 존재하며, 여행가는 등산을 하고자 한다. 여행가의 위치는 초기에 (1, 1)로 가장 왼쪽 위의 칸에 서 있으며, 결과적으로 가장 오른쪽 아래의 위치인 (N, N)의 위치로 이동하는 것이 목표다.

보드 판의 각 위치는 0 이상 100 이하의 정수로 표현되는데, 이것은 해당 위치의 고도(높이)를 의미한다. 시작 위치에 해당하는 (1, 1) 위치의 고도(높이) 값은 항상 0이며, 도착 위치인 (N, N)까지 최소한의 체력을 소모하여 이동하는 것이 목표다.

여행가는 자신의 위치에서 인접한 상, 하, 좌, 우 위치로 이동이 가능하다. 예를 들어 N=4인 상황을 가정하자. 이때, 여행가가 (1, 2)의 위치에 있다면 보드 판의 형태를 다음의 그림처럼 표현할 수 있을 것이다. 그림에서 여행가의 위치는 빨간색 음영으로 색칠하였고, 여행가가 이동 가능한 위치는 파란색 음영으로 색칠하였다.

위 표는 4행 4열 격자이다. 원본에서는 여행가의 위치와 이동 가능한 위치가 음영으로만 표시되어 있어, 텍스트 추출에서 셀 값이 전혀 남지 않았다.

여행가는 산을 벗어나지만 않는다면 현재 위치에서 인접한 위치(상, 하, 좌, 우)로 이동이 가능하다. 이때 현재 위치에서 인접한 위치 중 하나를 골라 다음 위치로 이동할 때, 고도가 다르더라도 이동이 가능하다. 단, 현재 위치와 이동할 인접 위치의 높이(고도)가 다르다면, 이동하기 위해 고도의 차이만큼 체력이 소모된다. 반면에 고도가 동일하다면 체력은 소모되지 않는다.

여행가가 (1, 1)의 위치에서 (N, N)의 위치로 이동하기 위한 체력 소모량의 최소 값을 계산하는 프로그램을 작성하여라.

N=5일 때의 한 예시를 확인해 보자. 보드 판에서 각 위치에 쓰인 값은 해당 위치의 고도(높이)를 의미한다. 시작 위치에 해당하는 (1, 1) 위치의 고도(높이) 값은 항상 0이다.

각 위치는 (행, 열)을 의미한다고 가정하자. 현재 예시에서는 (1, 1) → (2, 1) → (3, 1) → (4, 1) → (4, 2) → (5, 2) → (5, 3) → (5, 4) → (5, 5) 순서대로 이동하면, 총 체력 소모량은 5이다. 그림으로 표현하면, (1, 1)에서 (5, 5)의 위치까지 이동하는 최단 경로에 대하여 음영으로 칠하였고, 이동을 수행했을 때 체력 소모가 발생하는 칸에 대하여 파란색으로 칠하였다.

이와 같이 움직일 때 체력 소모량은 5이며, 이것보다 적게 체력을 소모할 수 있는 경우는 존재하지 않는다. (최소 체력 소모량) 따라서 본 예시에서의 정답은 5이다.

입출력 예시

예시 1

입력

5, [[0, 0, 0, 0, 1], [1, 1, 1, 0, 1], [1, 4, 4, 4, 4], [1, 1, 4, 3, 3], [0, 1, 3, 1, 1]]

출력

5

예시 2

입력

6, [[0, 5, 6, 2, 3, 8], [1, 1, 1, 1, 1, 1], [5, 6, 5, 3, 2, 3], [2, 6, 5, 2, 2, 4], [7, 7, 7, 3, 5, 6], [6, 7, 8, 4, 4, 3]]

출력

5

원본에서 모의고사 8회 3번입니다.