N × N 의 행렬로 지형도가 표시된 산이 있다.

행렬의 원소의 값은 양의 정수값으로 그 위치에서의 높이를 말해준다.

등산가들은 산의 바깥 지역(높이 0)으로부터 정상에 도달하기 위하여 가장 경제적인 루트를 탐색하려고 한다.

경제적인 경로란 힘을 가장 적게 들이고 정상까지 올라갈 수 있는 길을 말한다.

예를 보면서 설명해보자. 다음은 행렬 Mount[5,5]로 표시된 산악 지형이다.

산의 정상은 Mount[3,3]의 위치에 있으며, 그 높이는 6이다.

그리고 이 산의 바깥지 역은 모두 해발이 0이다.

등산가가 산에 오르는 시작점의 위치는 산의 바깥 지역의 어디에서 시작해도 좋다.

등산가는 어떤 한 지역에서 그 위치에 인접한 네 방향(위, 아래, 왼쪽, 오른쪽)으로만 움직일 수 있다.

인접한 지역으로 움직일 수 있는 경우는 (1) 평지로 이동할 경우, (2) 내려갈 경우, (3) 올라갈 경우의 세 가지이다.

이 세가지 경우에 필요한 "힘"의 양은 다음과 같이 표현될 수 있다.

(1) 인접한 같은 높이의 지역을 수평 이동할 경우에는 그냥 평지를 걸어가면 되므로 힘이 전혀 들지 않는다고 가정한다.
예를 들면 Mount[5,2]에서 Mount[5,3]으로 이동하는 경우와 Mount[4,5]에서 Mount[5,5]로 이동하는 경우에는 전혀 힘이 들지 않는다.
(2) 내리막길을 따라갈 경우(예를 들면, Mount[2,3]에서 Mount[2,2]로 갈 때)에는 그 높이 차이 만큼의 힘이 든다.
즉 이 경우에는 5-3=2만큼의 힘이 든다.
(3) 오르막길을 오를 경우에는 이동할 두 지역의 높이 차의 제곱 만큼의 힘이 든다.
즉 Mount[1,2]에서 Mount[1,3]으로 갈 경우는 (4-2)^2=4 만큼의 힘이 든다.

#1111 upload 3499회 done 961회 how_to_reg 635명

등산로 찾기 timer 1초 memory 64MB

#1111

등산로 찾기 1초 64MB