[BFS] 섬의 갯수

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

4963번: 섬의 개수

 

계속해서 반복하자. BFS 연습

여긴 특별히 대각선까지 포함한 유형이었음

from collections import deque
while True :
    N, M = [int(x) for x in input().split()]
    
    if (N,M) == (0,0):
        break

    maps = [ [int(x) for x in input().split()] for _ in range(M)]

    move_x = [-1,1,0,0,-1,1,-1,1]
    move_y = [0,0,-1,1,-1,1,1,-1]

    visited = [ [0]*N for _ in range(M) ]

    def BFS() :

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

            for i in range(8) :
                after_x = x+move_x[i]
                after_y = y+move_y[i]

                if after_x < 0 or after_y < 0 or after_x >= M or after_y >= N :
                    continue

                if visited[after_x][after_y] == 0 and maps[after_x][after_y] == 1 :
                    queue.append([after_x,after_y])
                    visited[after_x][after_y] = 1

    count = 0
    for i in range(M) :
        for j in range(N) :
            if maps[i][j] == 1 and visited[i][j] == 0 :
                queue = deque()
                queue.append([i,j])
                BFS()
                count+=1
    print(count)