목장수호 > 문제은행

본문 바로가기


문제은행

1096 : 목장수호

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



창호의 농장위에는 많은 언덕이 있고, 창호는 이곳에 자신이 아끼는 젖소들의 안전을 위해서 경비를 배치하고자 한다.

 

창호는 각 언덕 중에서 고도가 높은 곳에 경비를 하나씩 세우고자 할 때 얼마나 많은 경비가 배치해야 하는지가 궁금하다. 창호는 정수 행렬로 되어있는 지도를 가지고 있다. 행렬은 N(1<N≤700)개의 행과 M(1<M≤700)개의 열로 이루어져 있다. 행렬의 요소들 중 i번째 행의 j번째 열에 위치한 요소는 그 위치의 고도 Hij(0≤Hij≤10,000)을 뜻한다. 당신은 주어진 정보를 통해서 지도상에 존재하는 언덕의 꼭대기가 몇 개가 존재하는지를 찾아야 한다.

 

언덕의 꼭대기란, 행렬의 원소 중에서 고도가 같은 인접한 언덕들의 덩어리가 있을 때, 이 주변에 고도가 해당 덩어리보다 낮은 원소들만 존재할 경우 이러한 덩어리를 언덕의 꼭대기라 부른다. 그리고 임의의 원소가 인접하다는 것은 자신이 행렬에 속한 행의 위치가 i이고, 열의 위치가 j라고 하고, 다른 원소의 행과 열의 위치가 k, l 이라고 했을 경우 |i-k| <= 1 이고 |j-l| <= 1 인 언덕은 서로 인접해 있다고 한다.


입력의 첫 번째 줄에는 N과 M이 입력되어진다. 그 다음 줄부터 N+1개의 줄에는 행렬로 이루어진 고도의 정보가 입력되는데, i+1번째 줄은 행렬의 i번째 행을 뜻하며, 이 줄에는 M개의 정수 Hij가 인접한 숫자 사이에 공백을 두고 순서대로 들어온다.



언덕의 꼭대기의 갯 수를 출력한다.


[Copy]
8 7 
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0
[Copy]
3




Usaco 2008 Nov Bronze guard

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.