등산로 찾기 > 문제은행

본문 바로가기


알고리즘 최단거리

1111 : 등산로 찾기

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 453 회    시도횟수: 2004 회   



n×n의 형렬로 지형도가 표시된 산이 있다. 행렬의 원소의 값은 양의 정수값으로 그 위치에서의 높이를 말해준다. 등산가들은 산의 바깥지역(높이 0)으로부터 정상에 도달하기 위하여 가장 경제적인 루트를 탐색하려고 한다. 경제적인 경로란 힘을 가장 적게 들이고 정상까지 올라갈 수 있는 길을 말한다.


예를 보면서 설명해보자. 다음은 행렬 Mount[5,5]로 표시된 산악지형이다. 산의 정상은 Mount[3,3]의 위치에 있으며, 그 높이는 6이다. 그리고 이 산의 바깥지역은 모두 해발이 0이다. 등산가가 산에 오르는 시작점의 위치는 산의 바깥지역의 어디에서 시작해도 좋다.

 7ce7f2eba5731c8babe39036322897a0_1449816
등산가는 어떤 한 지역에서 그 위치에 인접한 네 방향(위, 아래, 왼쪽, 오른쪽)으로만 움직일 수 있다. 인접한 지역으로 움직일 수 있는 경우는 (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 만큼의 힘이 든다.

첫줄에는 산의 크기인 Mount[n,n]의 n값이 주어지고, 두 번째 줄에는 정상의 위치 Mount[i,j]의 i, j값이 주어진다.
단, Mount[n,n]에서 n은 100 이하이고, 각 지형의 최대 높이는 50 이하라고 가정한다.
그 다음 n개의 줄은 산의 크기에 따른 각 지점의 높이가 양의 정수값으로 주어진다.


첫째 줄에 정상까지 도달하는 가장 경제적인 경로를 따라 올라가는데 사용된 힘을 출력한다.

[Copy]
5
3 3
1 2 4 3 2
1 3 5 4 4
2 3 6 5 1
3 1 4 1 3
2 3 3 5 3
[Copy]
8



경로는 다음과 같다.
2[1,5]->3[1,4]->4[2,4]->5[3,4]->6[3,3]
= 2*2 + 1*1 + 1*1 + 1*1 + 1*1
= 8



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.