스키장 짓기 > 문제은행

본문 바로가기


문제은행

1028 : 스키장 짓기

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 6 회    시도횟수: 31 회   



농부 창호의 친한 동생 진욱이는 강원도의 산간지대에 산다. 그는 최근에 소들에게 스키 타는 법을 가르쳤다. 하지만 그의 소들은 다소 소심해서 많은 사람 앞에서 스키타고 싶지 않기 때문에 그는 그의 농장에 새로 스키를 탈 수 있는 스키장을 짓기로 했다.

 

진욱이가 만들게 되는 스키장은 너비 W 길이 L의 구역이다.(구역은 정사각형들로 구성되어 있으며 너비와 길이의 제한 조건은 다음과 같다.1≤W≤500 1≤L≤500). 각 정사각형 구역은 해발 H(0≤H≤9,999)의 높이를 가진다. 소들은 수평이나 수직으로 인접한 두 구역으로 스키를 타고 이동할 수 있는데 대각선 방향으론 이동할 수 없으며 또한 높은데서 낮은 곳이나 높이가 같은 곳 사이는 이동할 수 있지만 다른 방법으로는 이동할 수 없다.

 

진욱이는 스키와 스키리프트를 적절히 이용해서 어떤 지점에서도 다른 어떤 지점으로 이동할 수 있도록 하고 싶다. 스키 리프트는 높이에 관계없이 임의의 두 지점 사이를 연결하도록 지을 수 있다(또 양방향이다). 진욱이는 스키 리프트가 비싸기 때문에 최소 개수만을 사용해서 위와 같은 조건을 만족시키려고 한다.


첫 번째 줄에는 정수 W와 L이 공백을 사이에 두고 주어진다. 다음 줄부터 L줄에 걸쳐서 각 줄에 W개의 정수로 된 각 지점의 높이가 주어진다.



필요한 최소의 리프트 수를 출력한다.


[Copy]
9 3
1 1 1 2 2 2 1 1 1
1 2 1 2 3 2 1 2 1
1 1 1 2 2 2 1 1 1
[Copy]
3


(1,1)를 왼쪽 아래라고 표현 하면, 다음의 위치에 리프트를 지을 경우 최적이 된다. (3,1) <-> (8,2), (7,3)<->(5,2), (1,3)<->(2,2)






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.