[BFS] 백준 섬의 개수 2588번 with Python3

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

4963번: 섬의 개수

문제

 

내 풀이

import sys
from collections import deque
input = sys.stdin.readline

#     상 우 하 좌 좌상 좌하 우상 우하
dx = [-1, 0, 1, 0, -1,  1,   -1,  1]
dy = [0, 1, 0, -1, -1,  -1,  1,  1]


def bfs_2d(r, c):
    que = deque([])
    que.append([r, c])
    visited[r][c] = 1

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

            if (0 <= nx < h) and (0 <= ny < w) and visited[nx][ny] == 0 and sea[nx][ny] == 1:
                visited[nx][ny] = 1
                que.append([nx, ny])


while True:
    # 입력
    w, h = map(int, input().split())
    sea = [list(map(int, input().split())) for _ in range(h)]

    # 종료조건
    if w == 0 and h == 0:
        exit()

    visited = [[0] * (w) for _ in range(h)]
    count = 0

    for i in range(h):
        for j in range(w):
            if sea[i][j] == 1 and visited[i][j] == 0:
                bfs_2d(i, j)
                count += 1

    print(count)

해설

상우하좌 이동에서 대각선까지 포함하게된 문제. 크게 다를 점은 없다.