섬의 개수

1. 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.
2. 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다.

BFS

from collections import deque

# 이동 가능한 좌표 (상하좌우+대각선)
dx = [-1, -1, -1, 1, 1, 1,  0, 0]
dy = [-1, 0, 1, -1, 0, 1, -1, 1]

def BFS(x, y):
  queue = deque([[x, y]])
  # 탐색한 곳은 -1로 처리
  Map[x][y] = -1

  # 이어진 섬이 있으면 반복문을 돈다.
  while queue:
    x, y = queue.popleft()
    for i in range(8):
      nx = x + dx[i]
      ny = y + dy[i]
      # 갈 수 있는 영역에 대해
      if nx >= 0 and nx < h and ny >= 0 and ny < w:
        # 이어진 섬이 있으면
        if Map[nx][ny] == 1:
          # 탐색 처리하고 queue에 추가한다.
          Map[nx][ny] = -1
          queue.extend([[nx, ny]])

# 테스트 케이스별 탐색
while True:
  w, h = map(int, input().split())
  if w == 0 and h == 0:
    break
  Map = []
  ans = 0

  for _ in range(h):
    Map.append(list(map(int, input().split())))

  # 지도에서 섬을 찾으면 BFS 탐색 시작
  for i in range(h):
    for j in range(w):
      if Map[i][j] == 1:
        # 탐색을 진행한 횟수 = 섬의 개수
        BFS(i, j)
        ans += 1
  
  print(ans)

DFS

# 이동 가능한 좌표 (상하좌우+대각선)
dx = [-1, -1, -1, 1, 1, 1,  0, 0]
dy = [-1, 0, 1, -1, 0, 1, -1, 1]

def DFS(x, y):
  stack = [[x, y]]
  # 탐색한 곳은 -1로 처리
  Map[x][y] = -1

  # 이어진 섬이 있으면 반복문을 돈다.
  while stack:
    x, y = stack.pop()
    for i in range(8):
      nx = x + dx[i]
      ny = y + dy[i]
      # 갈 수 있는 영역에 대해
      if nx >= 0 and nx < h and ny >= 0 and ny < w:
        # 이어진 섬이 있으면
        if Map[nx][ny] == 1:
          # 탐색 처리하고 stack에 추가한다.
          Map[nx][ny] = -1
          stack = [[nx, ny]] + stack

while True:
  w, h = map(int, input().split())
  if w == 0 and h == 0:
    break
  Map = []
  ans = 0

  for _ in range(h):
    Map.append(list(map(int, input().split())))

  # 지도에서 섬을 찾으면 DFS 탐색 시작
  for i in range(h):
    for j in range(w):
      if Map[i][j] == 1:
        # 탐색을 진행한 횟수 = 섬의 개수
        DFS(i, j)
        ans += 1
  
  print(ans)