[Algorithm] 사과나무 (BFS)

상하좌우 방향을 이용하여 마름모 형태로 방문하는 방법.

문제를 기준으로 설명해보자면,

• L = 0 일 때는 노드 하나가 있다. -> (n//2, n//2)
• L = 1 일 때는 (n//2, n//2) 노드에서 4개(상하좌우)로 파생된 노드 4개가 있다. -> (n//2 -1, n//2) (n//2 +1, n//2) (n//2, n//2 -1) (n//2, n//2 +1)
• L = 2 일 때는 L = 1 에 있는 4개의 노드들 각각 4개씩 또 뻗어나가다보니, L = 2 의 노드는 총 16개 일 것이다.
  그런데 문제에서는 L = 1 까지 (노드가 4개인 레벨)까지만 필요하므로 L = 2 일 때 break 를 건다.

만약 더 큰 다이아몬드 구조로 넓히고 싶다면 L 을 계속 키우면 된다.

from collections import deque

# 최상단 노드는 n*n 격자판의 정중앙 좌표 값!

'''bfs 방식으로 풀기'''
def bfs(x, y):
    global s
    q = deque()
    q.append((x, y))
    visited[x][y] = 1
    s += lst[x][y]

    L = 0
    while True:
        if L==n//2:
            break
        size = len(q)  # pop 하기 전에 size 구하기
        # print("size", size)
        for i in range(size):
            tmp = q.popleft()
            for j in range(4):
                x = tmp[0] + dx[j]
                y = tmp[1] + dy[j]
                if visited[x][y] == 0:
                    visited[x][y] = 1
                    q.append((x, y))
                    s += lst[x][y]
        # print(L, tmp)
        # for i in range(len(visited)):
        #     print(visited[i])
        L += 1


n = int(input())
lst = [list(map(int, input().split())) for _ in range(n)]

visited = [[0]*n for _ in range(n)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
s = 0
bfs(n//2, n//2)
print(s)