마름모 모양으로 되어 있는 부분의 사과만 수확한 경우 총 몇 개의 사과를 딸 수 있는지 구해라
칸들 안에 들어있는 해당 숫자는 수확량이다.
문제 풀이
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을 사용한 최단거리를 구하는 문제입니다 또한 이 문제의 정확한 명칭은 다익스트라 알고리즘이라 합니다.
