[BOJ] 4963 / 섬의 개수 / Python 파이썬

[BOJ] 4963 / 섬의 개수 / Python 파이썬

[BOJ] 4963 / 섬의 개수 / Python 파이썬

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

4963번: 섬의 개수

 

풀이

주어진 이차원 배열에서 상하좌우 그리고 대각선으로 이어진 그룹의 개수를 구하는 문제이다.

 

인접한 섬을 찾는 방법은 이차원 배열에서의 기본 탐색 방법을 사용하였고 (dy, dx)

Queue 를 사용한 BFS 로 경로를 저장하여 탐색하였다.

 

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


def BFS(s_y, s_x):
    global w, h

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

    dq = deque()
    dq.append((s_y, s_x))

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

        for i in range(8):
            Y = y + dy[i]
            X = x + dx[i]
            if 0 <= Y < h and 0 <= X < w and maps[Y][X]:
                maps[Y][X] = 0
                dq.append((Y, X))


while True:
    w, h = map(int, input().split())
    if not w or not h:
        break
    maps = [0] * h

    for i in range(h):
        maps[i] = list(map(int, input().split()))
    res = 0
    for y in range(h):
        for x in range(w):
            if maps[y][x]:
                res += 1
                maps[y][x] = 0
                BFS(y, x)
    print(res)