[백준/Python] 4963 섬의 개수

 

• 2중포문으로 완전탐색을 하다가 섬을 만나게 되면 bfs를 이용하여 8방향으로 이어져있는 섬이라면 0으로 바꿔주면서 진행했다.

 

from collections import deque

while True:
    w,h = map(int,input().split())
    if w == 0 and h == 0: # 0,0이 입력되면 break
        break

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

    def bfs(j,i): # 인접한 섬을 전부 0 으로 바꿔주는 함수
        q = deque([(j,i)])

        directy = [-1,-1,-1,0,0,1,1,1]
        directx = [-1,0,1,-1,1,-1,0,1]

        while q:
            y,x = q.popleft()

            for k in range(8):
                dy = directy[k] + y
                dx = directx[k] + x

                if dy >= h or dy < 0 or dx >= w or dx < 0: # 배열 인덱스를 벗어난다면 continue
                    continue
                if arr[dy][dx] == 1:
                    arr[dy][dx] = 0
                    q.append([dy,dx])

    for j in range(h):
        for i in range(w):
            if arr[j][i] == 1: # 섬이 발견되면 본인을 0으로 만들고 bfs 함수 실행
                cnt += 1
                arr[j][i] = 0
                bfs(j,i)

    print(cnt)