BOJ - 4963 - 섬의 개수

Updated:

import sys
from queue import Queue

def BFS(W, H, Q, Check, Map):
    dx = [0, 0, 1, -1, 1, 1, -1, -1]
    dy = [1, -1, 0, 0, 1, -1, -1, 1]

    while (not Q.empty()):
        x, y = Q.get()

        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if(0 <= nx and 0<= ny and nx < H and ny < W):
                if (Check[nx][ny] == False and Map[nx][ny] > 0):
                    Check[nx][ny] = True
                    Q.put((nx, ny))

def solution():

    while True : 
        W, H = map(int, sys.stdin.readline().split())
        
        if W == 0 and H == 0:
            break
        
        Q = Queue()
        Map = []
        Check = [[False] * W for _ in range(H)]

        for _ in range(H):
            Map.append(list(map(int, sys.stdin.readline().split())))

        result = 0
        for i in range(H):
            for j in range(W):
                if Map[i][j] == 1 and Check[i][j] == False:
                    Q.put((i, j))
                    BFS(W, H, Q, Check, Map)
                    result += 1
    
        print(result)

solution()

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

Categories:

Updated:

Leave a comment