섬의 개수

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

요약
가로, 세로, 대각선으로 인접한 육지 칸을 하나의 섬으로 볼 때, 여러 격자 지도에서 섬의 개수를 센다.
난이도

쉬움10점 중 3점

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

문제

정사각형 칸으로 이루어진 섬과 바다의 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

어떤 칸에서 가로, 세로 또는 대각선으로 인접한 칸으로는 걸어서 이동할 수 있다. 즉, 한 칸은 최대 8개의 칸과 이어져 있다.

두 땅 칸이 같은 섬에 속하려면, 한 칸에서 다른 칸까지 땅 칸만 밟아 걸어갈 수 있는 경로가 존재해야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로는 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 ww와 높이 hh가 주어진다. ww와 hh는 5050 이하의 양의 정수이다.

둘째 줄부터 hh개의 줄에 걸쳐 지도가 주어지며, 각 줄에는 ww개의 정수가 공백으로 구분되어 주어진다. 11은 땅, 00은 바다를 뜻한다.

입력의 마지막 줄에는 00이 두 개 주어지며, 이 줄은 처리하지 않는다.

출력

각 테스트 케이스마다 섬의 개수를 한 줄에 하나씩 출력한다.

예제1

  1. 예제 1

    입력
    1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0
    예상 출력
    0
1
1
3
1
9