[Algorithms] 깊이/넓이 우선 탐색 (DFS, BFS) 활용-사과나무(BFS)

 

• 처음에 풀이 방식을 절반 먼저 사과 개수 계산하고, 나머지 거꾸로 시작해서 절반 전까지 더해서 계산하는 방법으로 풀이했었다.
• 해설을 듣고 나니, 무릎을 탁! 쳤다...  가운데 좌표점을 시작으로 십자 모양으로 뻗어나가면 되는 문제

import sys
from collections import deque
 
 
# sys.stdin=open('input', 'r')
n = int(input())
apple = [list(map(int, input().split())) for _ in range(n)]
check = [[0]*n for _ in range(n)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
 
cnt = 0
queue = deque()
queue.append((n//2, n//2))
level = 0
while queue:
    if level == n//2:
        break
    size = len(queue)
    for i in range(size):   # queue 안의 모든 요소가 pop 될 때까지
        cur = queue.popleft()
        for j in range(4):
            x = cur[0]+dx[j]
            y = cur[1]+dy[j]
            if check[x][y] == 0:
                check[x][y]=1
                queue.append((x,y))
                cnt += apple[x][y]
    level += 1
 
print(cnt)