[boj] 백준 4963 섬의 개수 python 풀이

풀이

bfs로 풀이함

 

문제

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

코드

import sys
input = sys.stdin.readline

move = {(-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1)}

def bfs(MAP, x, y):
    q = [(x,y)]
    MAP[x][y] = -1
    while q:
        x,y = q.pop(0)

        for tx, ty in move:
            nx = x + tx
            ny = y + ty

            if 0<=nx<h and 0<=ny<w and MAP[nx][ny] == 1:
                q.append((nx,ny))
                MAP[nx][ny] = -1 # visited

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

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

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