문제

• 주어진 그래프의 섬의 갯수를 구해라
• 섬은 상하좌우 대각선이 연결되어 있으면 하나의 섬으로 본다.

코드

from collections import deque

def BFS(x,y):
    q = deque()
    q.append((x,y))
    island[x][y] = 0
    while q:
        x, y = q.popleft()
        for i in range(8):
            nx = x+dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<n and island[nx][ny] == 1:
                island[nx][ny] = 0
                q.append((nx,ny))

    

if __name__ =="__main__":
    n = int(input())
    island = [list(map(int,input().split())) for _ in range(n)]
    dx = [0,0,-1,1,-1,-1,1,1]
    dy = [1,-1,0,0,1,-1,1,-1]
    cnt = 0
    for i in range(n):
        for j in range(n):
            if island[i][j] == 1:
                BFS(i,j)
                cnt += 1
    print(cnt)

풀이

• 기존 BFS로 푸는 문제에 대각선이라는 조건이 추가되었다.
  
• 해당 좌표만큼 확인을 하고 확인이 끝나면 하나의 섬으로 간주해서 cnt를 1씩 증가시켜준다.
• BFS와 deque를 사용한 문제 풀이에 익숙하다면 어렵지 않은 문제이다.