[BFS활용] - 섬나라 아일랜드

섬나라 아일랜드

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

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

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

만약 위와 같다면

 

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

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

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

 

▣ 입력예제 1

7

1 1 0 0 0 1 0

0 1 1 0 1 1 0

0 1 0 0 0 0 0

0 0 0 1 0 1 1

1 1 0 1 1 0 0

1 0 0 0 1 0 0

1 0 1 0 1 0 0

 

▣ 출력예제 1

5

 

 

나의 코드

from collections import deque
n=int(input())

arr=[list(map(int,input().split())) for _ in range(n) ]

dx=[-1,-1,0,1,1,1,0,-1]
dy=[0,1,1,1,0,-1,-1,-1]
dq=deque()
res=[]
cnt=0

for i in range(n):
    for j in range(n):
        if arr[i][j]==1:
            cnt+=1
            arr[i][j]=0
            dq.append([i,j])

            while dq:
                for w in range(len(dq)):
                    x,y=dq.popleft()

                    for k in range(8):
                        nx=x+dx[k]
                        ny=y+dy[k]
                        if 0<=nx<n and 0<=ny<n and arr[nx][ny]==1:
                            arr[nx][ny]=0
                            dq.append([nx,ny])
            

print(cnt)

방향벡터가 늘어난것 말곤 이전 문제와 완전 동일하다.

 

 

 

정답 코드

import sys
from collections import deque
sys.stdin=open("input.txt", "r")
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
Q=deque()
for i in range(n):
    for j in range(n):
        if board[i][j]==1:
            board[i][j]=0
            Q.append((i, j))
            while Q:
                tmp=Q.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
                        Q.append((x, y))
            cnt+=1
print(cnt)

나의 코드와 같다 !