코테준비/알고리즘

#4963 섬의 개수

아놀드금자 2023. 7. 30. 22:07
728x90
from collections import deque

#상하좌우 + 대각선
x = [1,0,-1]
y = [1,0,-1]

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

    maps = [list(map(int, input().split())) for _ in range(h)]
    check = [[0 for _ in range(w)] for _ in range(h)]
    land = 0


    for j in range(w):
        for k in range(h):

            if maps[k][j] == 1 and check[k][j] == 0:
                land += 1

                q = deque([[k, j]])
                check[k][j] = 1

                while q:
                    now = q.popleft()

                    for i in range(3):
                        for o in range(3):
                            next_x = now[0] + x[i]
                            next_y = now[1] + y[o]

                            if 0 <= next_x < h and 0 <= next_y < w:
                                if maps[next_x][next_y] == 1 and check[next_x][next_y] == 0:
                                    q.append([next_x, next_y])
                                    check[next_x][next_y] = 1

    print(land)
728x90