❗️[알고리즘]사과나무(BFS)

문제

현수의 농장은 N*N 격자판으로 이루어져 있으며, 각 격자안에는 한 그루의 사과나무가 심어저 있다. N의 크기는 항상 홀수이다. 가을이 되어 사과를 수확해야 하는데 현수는 격자판안의 사 과를 수확할 때 다이아몬드 모양의 격자판만 수확하고 나머지 격자안의 사과는 새들을 위해서 남겨놓는다.
만약 N이 5이면 아래 그림과 같이 진한 부분의 사과를 수확한다.

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

▣ 입력설명
첫 줄에 자연수 N(홀수)이 주어진다.(3<=N<=20)
두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 이 자연수는 각 격자안에 있는 사과나무에 열린 사과의 개수이다. 각 격자안의 사과의 개수는 100을 넘지 않는다.

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

입력예제 1

5
10 13 10 12 15
12 39 30 23 11
11 25 50 53 15
19 27 29 37 27
19 13 30 13 19

출력예제 1

379

[내 코드(틀린 코드)]

from collections import deque
import sys
sys.stdin=open("/Users/kimdoyeon/Desktop/pythonalgorithm_formac/섹션 7/8. 사과나무/in1.txt")

N=int(input())
a=[list(map(int,input().split())) for _ in range(N)]
sum=a[N//2][N//2]
ch=[[0]*N for _ in range(N)]
ch[N//2][N//2]=1
dx=[1,0,-1,0]
dy=[0,1,0,-1]
k=N//2
t=0
n=N

dQ=deque()
dQ.append([k,k])
for _ in range(N//2):
    now=dQ.popleft()
    for next in ((now[0]+dx[0],now[1]+dy[0]),(now[0]+dx[1],now[1]+dy[1]),(now[0]+dx[2],now[1]+dy[2]),(now[0]+dx[3],now[1]+dy[3])):
        if  ch[next[0]][next[1]]==0:
            dQ.append(next)
            ch[next[0]][next[1]]=1
            print(a[next[0]][next[1]])
            sum+=a[next[0]][next[1]]
print(sum)

1. BFS를 시작할 때 시작점을 행렬의 중앙부터 시작한다.
2. 중앙부터 상하좌우를 탐색하기위해 dx,dy를 배열형태로 저장
3. ch[N//2][N//2]=1를 통해서 시작점인 중앙부를 방문처리를 하고 시작

문제점
1.상하좌우형태로 N이 5일떄는 2번의 단계를,N이 7일 때는 3번의 단계를 거쳐 상하좌우탐색이 이루어져야 한다는 것을 알고는 있었지만 구현하지 못하였다.
2. 떄문에 탐색하는 곳을 출력해보면 한쪽만 탐색을 하는 문제점이 발생!

[헤설코드]

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)]
sum=0
Q=deque()
ch[n//2][n//2]=1
sum+=a[n//2][n//2]
Q.append((n//2,n//2))
L=0
while True:
	if L==n//2:
		break
    size=len(Q)
    for i in range(size):
    	tmp=Q.popleft()
        for j in range(4):
        	x=tmp[0]+dx[j]
            y=tmp[1]+dy[j]
            if ch[x][y]==0:
            	sum+=a[x][y]
                ch[x][y]=1
                Q.append((x,y))
    L+=1

1.while문 이전 코드는 내 코드와 동일
2. 위에서 내가 구현하지 못한 레벨 단계의 탐색 L==n//2
3. Q의 사이즈를 통해서 각각의 단계별로 Q에 삽입되어있는 좌표의 갯수만큼 상하좌우 탐색을 각각을 실행한다.
4.첫 번째 for문을 통해 해당 단계의 상하좌우 탐색 종료 시 L의 값을 1을 증가.