TIL - 2025.03.28

1. 2차원 배열 탐색 문제는 그래프로 모델링해서 BFS/DFS로 접근하면 깔끔하다.
2. 이 문제는 상하좌우뿐만 아니라 대각선까지 포함한 총 8방향 탐색이 핵심.
3. BFS 탐색 시, 방문한 위치를 바로 0으로 바꿔서 방문 처리하면 별도의 visited 배열이 필요 없다.
4. 입력이 여러 그룹으로 구성되어 있고, 각 그룹이 끝나는 조건(0 0 입력)을 주의해야 한다.
5. 입력이 많아질 수 있으므로 sys.stdin.readline()을 쓰는 것이 성능상 유리하다.

from collections import deque
import sys
input = sys.stdin.readline

# 8방향 탐색
dx = [-1, 1, 0, 0, -1, -1, 1, 1]
dy = [0, 0, -1, 1, -1, 1, -1, 1]

def bfs(x, y, graph, w, h):
    queue = deque()
    queue.append((x, y))
    graph[y][x] = 0

    while queue:
        cx, cy = queue.popleft()
        for d in range(8):
            nx, ny = cx + dx[d], cy + dy[d]
            if 0 <= nx < w and 0 <= ny < h and graph[ny][nx] == 1:
                graph[ny][nx] = 0
                queue.append((nx, ny))

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

    graph = [list(map(int, input().split())) for _ in range(h)]
    count = 0

    for y in range(h):
        for x in range(w):
            if graph[y][x] == 1:
                bfs(x, y, graph, w, h)
                count += 1

    print(count)