---

문제

• 마름모 모양으로 되어 있는 부분의 사과만 수확한 경우 총 몇 개의 사과를 딸 수 있는지 구해라
• 칸들 안에 들어있는 해당 숫자는 수확량이다.

---

문제 풀이

from collections import deque

n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
sum_apple = a[n//2][n//2]
ch = [[0]*n for _ in range(n)]
ch[n//2][n//2] = 1
dx = [0,0,-1,1]
dy = [1,-1,0,0]
q = deque()
q.append((n//2, n//2))
L = 0

while True:
    size = len(q)
    if L == n//2:
        break
    else:
        for i in range(size):
            apple = q.popleft()
            for j in range(4):
                nx = apple[0] + dx[j]
                ny = apple[1] + dy[j]
                if ch[nx][ny] == 0:
                    q.append((nx,ny))
                    ch[nx][ny] = 1
                    sum_apple += a[nx][ny]
    L += 1
    
print(sum_apple)

---

• 해당 문제는 정중앙부터 상하좌우를 둘러가며 n//2까지의 노드 Level을 확인해주는 작업을 진행하는 BFS 문제입니다.
• BFS는 DFS와 다르게 해당 레벨의 노드와 제일 가까운 자식 노드를 모두 확인해준 뒤 다음 자식의 자식 노드를 확인합니다.
• 이때 상하좌우를 사용하여 마름모 모양만 총 합에 더해주는 식의 진행을 하며 check를 위한 2차원 리스트 변수와 node Level 확인을 위한 변수 L을 사용하였습니다.
• 이 문제는 2차원 리스트의 시작 범위와 끝 범위를 잘 맞춰주면 또 풀 수 있는 문제지만 BFS 연습을 위해 BFS로 풀이를 진행했습니다.
• n//2 이전까지 노드레벨만 확인하는 이유는 위의 사진을 보면 알 수 있습니다. 상하좌우를 확인하기 때문에 해당 노드를 두 칸씩 확인하며 진행하기 때문입니다.

---

[본인의 지극히 개인적인 DFS BFS 문제 느낀점]

• DFS, BFS는 트리나 그래프를 도는 문제이기 때문에 노드의 흐름을 생각하고 진행해야 합니다.
• DFS는 깊이 우선 탐색이라는 이름에 맞게 가까운 노드의 자식 노드 또 그 노드의 자식노드 이런식으로 진행함을 유의하며 진행하고 stack 자료구조를 사용한다는 점을 잊지 않고 복기하며 풀어야 합니다.
• BFS는 거리를 구하는 문제에 적합하며 distance를 따로 저장할 수 있는 변수를 선언하여 여기에 거리를 넣어주는 연습을 하는 것이 중요합니다. 이때 BFS는 queue라는 자료구조를 쓰고 파이썬에서는 deque를 사용해 문제를 푸는 것이 일반적입니다. 이는 다음과 같은 이유 때문입니다.
• 리스트는 동적 배열로 구현되어 큐의 연산을 수행하기엔 효율적이지 않기 때문입니다. (popleft()와 appendleft()는 deque에서 지원합니다.)
• BFS는 해당 노드에 가까운 자식 노드를 전부 확인하고 다음 자식노드를 확인하는 식이기에 거리를 구하는 문제에 적합합니다.
• 이때 거리가 가중치가 있고 이 가중치가 음의 수가 아니라면 이는 heap을 사용한 최단거리를 구하는 문제입니다 또한 이 문제의 정확한 명칭은 다익스트라 알고리즘이라 합니다.