70)섬나라 아일랜드(BFS 활용)

문제

섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하기

 

조건

섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다.

 

각 섬은 1로 표시되어 상하좌우와 대 각선으로 연결되어 있으며, 0은 바다입니다.

 

제한사항

첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다.

 

두 번째 줄부터 격자판 정보가 주어진다.

 

첫 번째 줄에 섬의 개수를 출력한다.

 

문제풀이

from collections import deque

dx=[-1, -1, 0, 1, 1, 1, 0, -1]
dy=[0, 1, 1, 1, 0, -1, -1, -1]
N=int(input())
board=[list(map(int, input().split())) for _ in range(N)]
cnt=0
dQ=deque()

for i in range(N):
  for j in range(N):
    if board[i][j]==1:
      board[i][j]=0
      dQ.append((i, j))
      
      while dQ:
        tmp=dQ.popleft()
        for k in range(8):
          x=tmp[0]+dx[k]
          y=tmp[1]+dy[k]

          if 0<=x<N and 0<=y<N and board[x][y]==1:
            board[x][y]=0
            dQ.append((x, y))
      cnt+=1

print(cnt)