우주의 IT 소행성

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

# 좌, 우, 상, 하, 좌상대각, 우상대각, 좌하대각, 우하대각
move_x = [0, 0, -1, 1, -1, -1, 1, 1]
move_y = [-1, 1, 0, 0, -1, 1, -1, 1]


def bfs(i, j):
    graph[i][j] = 0
    queue = deque()
    queue.append((i, j))

    while queue:
        x, y = queue.popleft()
        for i in range(8):
            nx = move_x[i] + x
            ny = move_y[i] + y
            if 0 <= nx < h and 0 <= ny < w and graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))

while True:
    count = 0
    w, h = map(int, input().split())
    if w == h == 0:
        break
    graph = [list(map(int, input().split())) for _ in range(h)]

    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:
                bfs(i, j)
                count += 1
    print(count)

1. 맵의 모든 부분을 돌면서 육지일 때 너비 우선 탐색을 실행 ( 카운트 + 1 )

2. 너비 우선 탐색시 인접한 모든 섬을 방문하여 0 으로 만듦

3. 섬이 이어지지 않을 경우 다시 1로 돌아감

4. 다시 섬을 구해서 그 섬과 이어진 부분을 전부 0 으로 만듦 ( 카운트 + 1 )

... 위를 반복해서 이어진 섬을 찾는 것

KEY POINT > 이미 탐색된 섬 전체를 0으로 만들어 메인에서 bfs 하지 않게 만들어야 함