[인프런] 사과나무(BFS로 풀기)

---

문제설명

저번에 구현 유형으로 풀어본 사과나무 문제랑 동일하다. 하지만 BFS로 풀어야 한다.

https://techblog-history-younghunjo1.tistory.com/377

[인프런] 사과나무(다이아몬드)

사고과정

• 문제에서 요구하는 영역을 어떻게 상태트리로 만들어야 할지 도저히 몰랐다. 그래서 강의를 보고 아이디어만 보고 어느정도 구현은 했는데, BFS하는 레벨을 도중에 중간에 멈추는 것을 어떤 방식으로 해야할지에서 또 막혔다..
• 강의를 보았고 상태트리의 레벨 마다 그 때 레벨에서 큐의 길이만큼 BFS 탐색을 반복해서 수행하면 되었다.. 진짜 아이디어에 감탄했다..
• 아직은 BFS로 상태트리를 만드는 게 어색하다..더 연습해야겠다..!

풀이(스스로 못 푼 풀이)

from collections import deque

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
visited = [[0] * n for _ in range(n)]
# 초기 좌표
x = y = n//2
visited[x][y] = 1
queue = deque([(x, y)])
cnt = arr[x][y]
result = [(x, y)]
# 상,하,좌,우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 상태트리 레벨 정의
L = 0
while True:
    if L == n//2:
        break
    size = len(queue) 
    for _ in range(size):
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if visited[nx][ny] == 0:
                visited[nx][ny] = 1
                cnt += arr[nx][ny]
                queue.append((nx, ny))
    L += 1
print(cnt)