BOJ 4963 - 섬의 개수

문제

백준 온라인 저지 - 4963번

풀이 과정

섬과 바다의 지도가 주어질 때 섬의 개수를 구하는 문제입니다.
BFS 를 이용해서 컴포넌트의 개수를 구해주면 됩니다.

코드

import sys
from collections import deque


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


def in_range(x, y):
    return 0 <= x < H and 0 <= y < W


def bfs(x, y, visit):
    q = deque()

    visit[x][y] = 1
    q.append([x, y])

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

        for i in range(8):
            nx, ny = x + dx[i], y + dy[i]

            if in_range(nx, ny) and board[nx][ny] and not visit[nx][ny]:
                visit[nx][ny] = 1
                q.append([nx, ny])


def solution():
    island = 0
    visit = [[0] * W for _ in range(H)]

    for x in range(H):
        for y in range(W):
            if board[x][y] and not visit[x][y]:
                island += 1
                bfs(x, y, visit)

    return island


if __name__ == '__main__':
    while True:
        W, H = list(map(int, sys.stdin.readline().split()))

        if [W, H] == [0, 0]:
            break

        board = [list(map(int, sys.stdin.readline().split())) for _ in range(H)]
        answer = solution()
        print(answer)