농장의 언덕 지키기

면접 대비

시간 제한1초메모리 제한128 MB

요약
8방향으로 인접한 같은 높이의 칸들을 하나의 무리로 묶고, 그 무리가 더 낮은 높이나 지도 경계로만 둘러싸인 개수를 센다.
난이도

보통10점 중 4점

유형
그래프, DFS, BFS, 구현
정답자
아직 제출이 없습니다

문제

농장에는 언덕이 여러 개 있고, 농부 John은 소중한 젖소들을 지키기 위해 각 언덕의 꼭대기마다 경비원을 한 명씩 세우려고 한다. 모든 언덕 꼭대기에 경비원을 배치하려면 몇 명이 필요한지, 즉 지도에 언덕 꼭대기가 몇 개나 있는지 구하여라.

지도는 NN개의 행과 MM개의 열로 이루어진 정수 행렬로 주어진다 (1<N≤7001 < N \le 700, 1<M≤7001 < M \le 700). 행렬의 각 원소는 고도 HijH_{ij}를 나타내며 0≤Hij≤100000 \le H_{ij} \le 10000이다.

언덕 꼭대기란 값이 모두 같은 하나 이상의 인접한 칸들의 집합으로서, 그 집합의 바깥쪽 경계가 오직 지도의 가장자리이거나 자신보다 고도가 낮은(더 작은) 칸으로만 둘러싸여 있는 것을 말한다. 두 칸이 인접하다는 것은 두 칸의 행 좌표 차이의 절댓값이 11 이하이고 열 좌표 차이의 절댓값도 11 이하인 경우를 뜻한다(즉 상하좌우와 대각선을 포함한 8방향).

입력

  • 첫째 줄: 공백으로 구분된 두 정수 NN과 MM.
  • 둘째 줄부터 N+1N+1째 줄까지: i+1i+1번째 줄에는 행렬의 ii번째 행이 MM개의 정수 HijH_{ij}로 공백으로 구분되어 주어진다.

출력

  • 첫째 줄에 언덕 꼭대기의 개수를 하나의 정수로 출력한다.

힌트

예제 입력에서 언덕 꼭대기는 모두 3개이다: 왼쪽 위의 고도 44인 칸, 아래쪽에 있는 고도 22인 칸들 중 하나, 그리고 오른쪽 위 모서리의 고도 11인 칸이다.

예제1

  1. 예제 1

    입력
    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
    
    예상 출력
    3