Part6.13_완전탐색_깊이,넓이 우선탐색활용_섬나라 아일랜드(BFS)

이 문제는 8방향을 탐색한다.
이 문제는 전 문제 연습이다.

선생님 코드

import sys
sys.stdin = open("input.txt", "rt")
from collections import deque
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)

좋은 웹페이지 즐겨찾기