[알고리즘] 섬나라 아일랜드(BFS 활용)

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

---

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

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

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

만약 위와 같다면

입력설명

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

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

출력설명

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

테스트케이스

입력예제	출력예제
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	5
5 0 0 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 1 1 0 0 0	2
10 0 0 0 0 1 0 0 1 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0 1 1 1 0 0 1	5
15 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0	16

---

해결방법

1. 상하좌우 대각선 까지 살피는 리스트를 생성
2. 전체 좌표를 1번 씩 돌면서 해당 부분이 1인지 확인
3. 1일 경우 bfs를 이용하여 1인 곳을 찾아서 0으로 만든다 만약 bfs를 통한 큐안에 값이 없을 경우 count를 1 더한다
4. 반복하여 좌표의 끝까지 확인 후, 끝낸다.

   동작 시각화

---

코드

from collections import deque

# 상, 우, 하, 좌 (대각선 포함)
dx = [-1, 0, 1, -1, 1, -1, 0, 1]
dy = [-1, -1, -1, 0, 0, 1, 1, 1]

# n x n
n = int(input())

# 값 입력
land = [list(map(int,input().split())) for _ in range(n)]
ch_land = [[0] * n for _ in range(n)]

dQ = deque()

count = 0

for x in range(n):
    for y in range(n):
        # 만약 섬일 경우 값 넣기
        if land[x][y] == 1:
            dQ.append((x, y))
            land[x][y] = 0
            while dQ:
                size = len(dQ)
                now = dQ.popleft()
                for i in range(size):
                    for j in range(8):
                        # 좌표 안에 있을 경우
                        # 8 방향 확인
                        if 0 <= now[0] + dx[j] < n and 0 <= now[1] + dy[j] < n:
                            # 섬일 경우
                            if land[now[0] + dx[j]][now[1] + dy[j]] == 1:
                                land[now[0] + dx[j]][now[1] + dy[j]] = 0
                                dQ.append((now[0] + dx[j], now[1] + dy[j]))
            count = count + 1

print(count)