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

문제

섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 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

 

<풀이>

해당 문제같은경우 그렇게 어렵지 않다. 이중for문을 돌면서 L[0][0] 이 1인지 부터 확인을 한다 만약1이면 해당 리스트의 인덱스들을Queue(Q)에 넣고 while문을 돌거다 그 후 Q 부터 해서 상하좌우 그리고 대각선까지 확인을 한다.  1이 나올때 Q에 해당인덱스들을 넣는다. 그렇게 해서 while문이 끝나면 인접한 모든 1을 찾은것이므로 cnt 를 1개 증가시킨다. (단 참고로 체크한 값들은 0으로 바꿔준다)

from collections import deque
n = int(input())
L=[list(map(int,input().split())) for _ in range(n)]
#print(L)
dx = [0,-1,0,1]
dy = [1,0,-1,0]
dix = [1,1,-1,-1] # 대각선
diy = [-1,1,-1,1] # 대각선 
cnt = 0 # 섬 개수 카운트
Q = deque()
for i in range(n):
    for j in range(n):
        if L[i][j] == 1:
            L[i][j] = 0
            Q.append((i,j))
            while Q:
                tmp = Q.popleft()
                for k in range(4):
                    x = tmp[0] + dx[k] #상하좌우
                    y = tmp[1] + dy[k]
                    ix = tmp[0] + dix[k] #대각선
                    iy = tmp[1] + diy[k]
                    if 0<= x < n and 0<= y < n and L[x][y] == 1:
                        L[x][y] = 0
                        Q.append((x,y))
                    if  0<= ix < n and 0<= iy < n and L[ix][iy] == 1:
                        L[ix][iy] = 0
                        Q.append((ix,iy))
            cnt += 1
print(cnt)