[Baekjoon] 4963. 섬의 개수 - python

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

4963번: 섬의 개수

코드

from collections import deque

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

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

while True:
    w,h = map(int, input().split())
    if w == 0 and h == 0:
        break

    graph = []
    for _ in range(h):
        graph.append(list(map(int, input().split())))

    cnt = 0
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:
                bfs(i,j)
                cnt += 1
    print(cnt)

처음에 기본 bfs라고 생각하고 풀었는데

문제를 다시 읽어보니 “대각선”도 걸어갈 수 있는 사각형이였음

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

이렇게 바꿔줌으로서 문제 해결 ~>>