8. 사과나무(BFS) -섹션3 봉우리 참고

문제 - 생략

 

 

문제풀이 

import sys
from collections import deque
sys.stdin=open("input.txt", "r")
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                   #L은 최상위 노드의 부모이면서 step의 출발점 이므로 0으로 세팅한다. 

while True:
    if L==n//2:
        break
    size=len(Q)
    for i in range(size):   #★ 레벨0일때 레벨1탐색을 마침, 레벨1 일때 레벨 2탐색을 마침
        tmp=Q.popleft()     #tmp에는 튜플 1개만 저장된다
        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)