파이썬 알고리즘-61 (DFS/BFS 활용) 사과나무

61.사과나무(BFS)
현수의 농장은 N*N 격자판으로 이루어져 있으며, 각 격자안에는 한 그루의 사과나무가 심어저있다. N의 크기는 항상 홀수이다. 가을이 되어 사과를 수확해야 하는데 현수는 격자판안의 사과를 수확할 때 다이아몬드 모양의 격자판만 수확하고 나머지 격자안의 사과는 새들을 위해서남겨놓는다.만약 N이 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
현수과 수확하는 사과의 총 개수를 출력하세요.

▣ 입력설명
첫 줄에 자연수 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

n=int(input())
lst=[]
for i in range(n):
    tmp=(list(map(int, input().split())))
    tmp.insert(0,0)
    tmp.append(0)
    lst.append(tmp)
lst.insert(0,[0]*(n+2))
lst.append([0]*(n+2))
dq=deque()
dq.append([1,(n//2)+1])
ch=[0]*(n*n)
sum=0
while dq:
    now=dq.popleft()
    ch.append(now)
    if now[0]==n:
        break
    for i in range(1,n):
        now[0]+=i
        for j in (-1,0,1):
            now[1]+=j
            if now not in ch:
                print(now)
                dq.append(lst[now[0]][now[1]])
                sum+=lst[now[0]][now[1]]

print(sum)

격자의 가장 위의 가운데부터 시작해 x좌표에는 항상 1을 더하고 y좌표에는 -1,0,1을 더하려는 의도였는데, 무엇하나 제대로 되지 않았다.

풀이

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)]
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
print(sum)

반성점

• 가운데서 시작해서 상하좌우로 더해나가는 방법은 전에 이미 했던 방법인데 전혀 생각나지 않았다.

배운 것