[백준] 4963번 섬의 개수 (파이썬)

전민기·2023년 5월 8일
0

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

BFS

from collections import deque

dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

def bfs(graph, x, y):
    queue = deque()
    queue.append([x, y])
    graph[x][y] = 0
    
    while queue:
        x, y = queue.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx > h-1 or ny < 0 or ny > w-1:
                continue
            elif graph[nx][ny] == 0:
                continue
            elif graph[nx][ny] == 1:
                queue.append([nx, ny])
                graph[nx][ny] = 0

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        break
    else:
        graph = []
        for _ in range(h):
            graph.append(list(map(int, input().split())))
            
        cnt = 0
        for i in range(h):
            for j in range(w):
                if graph[i][j] == 1:
                    bfs(graph, i, j)
                    cnt += 1
        print(cnt)

0개의 댓글