백준 파이썬 4963 섬의 개수 - 파이썬(bfs/dfs)

bfs탐색 알고리즘을 통해서 풀 수 있는 문제다.

이 문제에서 신경써야 하는 부분은 보통은 상하좌우만 탐색을 하는 문제가 많았는데 이번 문제는 대각선까지 탐색을 해야 한다.

 

# 4963번: 섬의 개수

# 상하좌우대각선까지
dx = [0,0,-1,1,1,1,-1,-1]
dy = [1,-1,0,0,1,-1,1,-1]

from collections import deque

def bfs(w,h):
    cnt = 0
    for x in range(h):
        for y in range(w):
            if graph[x][y] == 1:
                cnt += 1
                q = deque()
                q.append([x,y])
                while q:
                    a,b = q.popleft()
                    for i in range(8):
                        nx = a + dx[i]
                        ny = b + dy[i]
                        if 0 <= nx < h and 0 <= ny < w:
                            if graph[nx][ny] == 1:
                                graph[nx][ny] = 0
                                q.append([nx,ny])
    print(cnt)

while True:
    w,h = map(int,input().split())
    if w == 0 and h == 0:
        break
    graph = []
    for i in range(h):
        graph.append(list(map(int,input().split())))

    bfs(w,h)