코테준비/알고리즘

#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

'코테준비 > 알고리즘' 카테고리의 다른 글

백트래킹  (0) 2023.08.24
DP 다이나믹 프로그래밍  (0) 2023.08.09
#2178 미로탐색  (0) 2023.07.27
2차원 리스트를 90도 회전하는 함수  (0) 2023.07.08
키패드누르기  (0) 2023.06.17