068 - 섬나라 아일랜드(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
#import sys
#sys.stdin = open('in.txt', 'rt')


def BFS():
    global cnt

    while dq:
        tmp = dq.popleft()
        cnt += 1
        x1 = tmp[0]
        y1 = tmp[1]

        for k in range(8):
            x = x1+dx[k]
            y = y1+dy[k]
            if 0 <= x < n and 0 <= y < n and a[x][y] == 1:
                a[x][y] = island
                dq.append((x, y))


if __name__ == '__main__':
    n = int(input())
    a = [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]
    cnt = 0
    island = 1
    res = list()
    dq = deque()
    for i in range(n):
        for j in range(n):
            if a[i][j] == 1:
                island += 1
                a[i][j] = island
                dq.append((i, j))
                cnt = 0
                BFS()
                res.append(cnt)
    print(len(res))
    # for x in a:
    #     print(x)