정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.
한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.
두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.
import sys
# 런타임 에러 (RecursionError)
sys.setrecursionlimit(5000)
def input():
return sys.stdin.readline().rstrip()
def dfs(x, y):
global answer, graph
graph[x][y] = 0
for i in range(8):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < m and 0 <= ny < n:
if graph[nx][ny]:
dfs(nx, ny)
# 상,하, 좌, 우, 대각선 4방향(왼쪽 위, 왼쪽 아래, 오른쪽 아래, 오른쪽 위)
dx, dy = (-1, 1, 0, 0, -1, 1, 1, -1), (0, 0, -1, 1, -1, -1, 1, 1)
while True:
answer = 0
n, m = map(int, input().split())
if n == 0 and m == 0:
break
graph = [[] for _ in range(m)]
for i in range(m):
graph[i] = list(map(int, input().split()))
for i in range(m):
for j in range(n):
if graph[i][j]:
dfs(i, j)
answer += 1
print(answer)