나쁜 풀

면접 대비

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

요약
격자에서 0이 아닌 칸들을 가로, 세로, 대각선으로 인접한 것끼리 이어 붙일 때 생기는 연결 요소의 개수를 센다.
난이도

쉬움10점 중 3점

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

문제

베시(Bessie)는 목장에서 풀을 뜯고 있다. 기준 높이(고도 0)에 있는 넓은 평지의 풀만 부드럽고 맛있으며, 고도가 1미터라도 높아지면 풀이 질겨져 맛이 없어진다. 고도가 높을수록 풀은 점점 더 맛이 없어진다.

맛없는 풀은 언덕의 경사면에서 자라며, 부드럽고 맛있는 풀의 바다 속에서 여러 개의 '섬'처럼 무리를 이룬다. 베시는 자신의 목장에 맛없는 풀의 섬이 몇 개나 있는지 세어 보기로 했다.

목장을 RR개의 행과 CC개의 열로 이루어진 1m×1m1\text{m} \times 1\text{m} 크기의 정사각형 격자로 나누고, 각 칸의 기준 높이 대비 고도를 재어 음이 아닌 정수로 반올림했다. 맛있는 풀이 있는 칸의 고도는 모두 0이다.

두 칸이 상하, 좌우, 또는 대각선 방향으로 인접해 있으면 같은 섬에 속한 것으로 본다. 고도가 0이 아닌 칸(맛없는 풀)들이 이루는 섬이 모두 몇 개인지 구하여라.

제약: 1<R≤10001 < R \le 1000이고 1<C≤10001 < C \le 1000이다.

입력

첫째 줄에 두 정수 RR과 CC가 공백으로 구분되어 주어진다.

다음 RR개의 줄 중 ii번째 줄에는 지도의 ii번째 행을 나타내는 CC개의 정수가 공백으로 구분되어 주어진다.

출력

섬의 개수를 나타내는 정수 하나를 출력한다.

힌트

예제에서는 섬이 두 개다. 왼쪽 영역을 크게 차지하며 대각선 인접을 통해 아래쪽까지 이어지는 큰 섬 하나와, 오른쪽 위 모서리에 있는 작은 섬 하나다.

예제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
    
    예상 출력
    2