6094 : 섬 개수 — 0-1 행렬 연결 요소
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
0과 1로 구성된 N×M 크기의 지도 행렬이 주어집니다. 1은 육지를 나타내고 0은 바다를 나타냅니다.
상하좌우로 연결된 육지(1)들의 묶음을 하나의 '섬'이라고 정의할 때, 지도에 존재하는 섬의 총 개수를 구하는 프로그램을 작성하십시오. (대각선으로 인접한 육지는 연결된 것으로 보지 않습니다.)
[제약 조건]
• 지도 크기: $1 \le N, M \le 1{,}000$ (정수)
• 각 칸: 0(바다) 또는 1(육지)
• 대각선 인접은 연결로 보지 않습니다.
상하좌우로 연결된 육지(1)들의 묶음을 하나의 '섬'이라고 정의할 때, 지도에 존재하는 섬의 총 개수를 구하는 프로그램을 작성하십시오. (대각선으로 인접한 육지는 연결된 것으로 보지 않습니다.)
[제약 조건]
• 지도 크기: $1 \le N, M \le 1{,}000$ (정수)
• 각 칸: 0(바다) 또는 1(육지)
• 대각선 인접은 연결로 보지 않습니다.
입력 설명
첫째 줄에 지도의 세로 크기 N과 가로 크기 M (1 ≤ N, M ≤ 1,000)이 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 지도의 정보가 공백으로 구분되어 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 지도의 정보가 공백으로 구분되어 주어집니다.
출력 설명
섬의 개수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
지도 상의 1인 칸 중 방문하지 않은 칸을 시작점으로 상하좌우 DFS 탐색을 하여 연결된 모든 육지를 방문 처리하고, DFS의 시작 횟수를 셉니다.