[Python Algorithm] 깊이/넓이 우선탐색(DFS, BFS) - 섬나라 아일랜드(BFS)

> 깊이/넓이 우선탐색(DFS, BFS) 활용 (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

 

import sys
input = sys.stdin.readline
from collections import deque

dx = [1, 0, -1, -1, -1, 0, 1, 1]
dy = [1, 1, 1, 0, -1, -1, -1, 0]
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)

 

 

⭐️ Point ! ⭐️

• 상하좌우 4방향이 아닌 대각선까지 8개의 방향을 검색한다 !

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이