65)사과나무(BFS)

문제

현수과 수확하는 사과의 총 개수를 출력하세요.

 

조건

현수의 농장은 N*N 격자판으로 이루어져 있으며, 각 격자안에는 한 그루의 사과나무가 심어저 있다.

 

N의 크기는 항상 홀수이다.

 

가을이 되어 사과를 수확해야 하는데 현수는 격자판안의 사과를 수확할 때 다이아몬드 모양의 격자판만 수확하고 나머지 격자안의 사과는 새들을 위해서 남겨놓는다.

 

만약 N이 5이면 아래 그림과 같이 진한 부분의 사과를 수확한다.

 

 

제한사항

첫 줄에 자연수 N(홀수)이 주어진다.(3<=N<=20) 두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다.

 

이 자연수는 각 격자안에 있는 사과나무에 열린 사과의 개수이다.

 

각 격자안의 사과의 개수는 100을 넘지 않는다.

 

수확한 사과의 총 개수를 출력합니다.

 

문제풀이

from collections import deque

dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
N=int(input())
a=[list(map(int, input().split())) for _ in range(N)]
ch=[[0]*N for _ in range(N)]
tsum=0
dQ=deque()
ch[N//2][N//2]=1
tsum+=a[N//2][N//2]
dQ.append((N//2, N//2))
L=0

while True:
  if L==N//2:
    break
  
  size=len(dQ)

  for i in range(size):
    tmp=dQ.popleft()
    for j in range(4):
      x=tmp[0]+dx[j]
      y=tmp[1]+dy[j]
      if ch[x][y]==0:
        tsum+=a[x][y]
        ch[x][y]=1
        dQ.append((x, y))
  L+=1

print(tsum)