[김태원 알고리즘] 사과나무 (BFS)

✍️ 문제 요약

- 항상 홀수인 N에 대해, N * N 격자판이 주어질 때, 다이아몬드 모양의 격자의 합을 구하여라.

 

💪 무식하게 풀기 (반복문)

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

ans = 0
src, dst = N//2, N//2
for i in range(N//2 + 1):
    for j in range(src, dst+1):
        ans += board[i][j]
    src, dst = src-1, dst+1

src, dst = 1, N-2
for i in range(N//2 + 1, N):
    for j in range(src, dst+1):
        ans += board[i][j]
    src, dst = src+1, dst-1

print(ans)

 

✨ 우아하게 풀기 (BFS)

- BFS를 사용하면, 다이아몬드 모양으로 진행한다.

    - 따라서 큐(queue)에 격자판의 중심을 담고, BFS를 적용하여 다이아몬드 모양으로 진행하자! 

- BFS를 언제까지 적용해야할까❓

    - BFS에 현재 레벨(`L`)을 담는다. 그리고 다음 레벨(`L+1`)이 `N//2`보다 작거나 같을 때에만 큐에 넣는다.

- 방문(`visited`) 리스트를 두고, 방문한 좌표에 또 다시 방문하지 않도록 한다.

- 다이아몬드 모양의 격자의 합을 구하기 위해서는, 방문한 좌표에 해당하는 값을 `tot`에 누적해야 한다.

from collections import deque

N = int(input())
lst = [list(map(int, input().split())) for _ in range(N)]
visited = [[0] * N for _ in range(N)]

q = deque()
q.append((0, N//2, N//2)) # (레벨, x좌표, y좌표)
visited[N//2][N//2] = 1 # 방문
tot = lst[N//2][N//2] # 합

dx, dy = [0,-1,0,1], [1,0,-1,0]
while q:
    L, x, y = q.popleft()
    for w in range(4):
        LL, xx, yy = L+1, x+dx[w], y+dy[w]
        if LL > N // 2: continue # 레벨이 N//2보다 크면 stop
        if xx < 0 or xx >= N or yy < 0 or yy >= N: continue
        if visited[xx][yy] == 1: continue
        visited[xx][yy] = 1 # 방문
        tot += lst[xx][yy] # 합
        q.append((LL, xx, yy))

print(tot)