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

(문제) 사과나무(BFS)

---

현수의 농장은 N * N 격자판으로 이루어져 있으며, 각 격자안에는 한 그루의 사과나무가 심어저 있다.

N의 크기는 항상 홀수이다.

가을이 되어 사과를 수확해야 하는데 현수는 격자판안의 사과를 수확할 때 다이아몬드 모양의 격자판만 수확하고 나머지 격자안의 사과는 새들을 위해서 남겨놓는다.

만약 N이 5이면 아래 그림과 같이 진한 부분의 사과를 수확한다.

현수가 수확하는 사과의 총 개수를 출력하세요.

입력설명

첫 줄에 자연수 N(홀수)이 주어진다. (3<=N<=20)

두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다.

이 자연수는 각 격자안에 있는 사과나무에 열린 사과의 개수이다.

각 격자안의 사과의 개수는 100을 넘지 않는다.

출력설명

수확한 사과의 총 개수를 출력합니다.

테스트케이스

입력예제	출력예제
5 10 13 10 12 15 12 39 30 23 11 11 25 50 53 15 19 27 29 37 27 19 13 30 13 19	379
7 74 10 31 26 59 16 89 78 44 49 1 64 33 15 9 95 70 18 22 25 40 62 77 28 3 78 75 23 82 38 20 16 42 1 79 1 24 2 25 95 26 79 4 35 46 94 70 44 83	1049
9 64 8 59 87 94 71 66 4 9 38 21 30 24 33 65 7 79 27 99 10 78 74 84 32 33 74 30 4 6 69 53 100 15 23 15 88 22 88 8 3 62 75 46 4 41 39 64 7 75 91 26 83 32 41 100 98 20 100 18 39 90 60 56 56 30 94 29 81 76 96 50 11 66 88 88 95 13 56 29 13 31	1991

---

해결방법

1. BFS를 이용하기 위해 중앙의 좌표부터 시작을 하여 “상, 우, 하, 좌” 순으로 좌표를 append 하고 전에 있던 값은 pop 시킨다.
2. 상하좌우의 좌표를 넣기 위해서 dx, dy라는 리스트를 이용하여 각 부분을 4번 반복하도록 코드를 작성한다.
3. 들렸던 곳 또한 체크하기 위해 체크 리스트를 생성한다.
4. 큐에 append를 시킬 경우 해당 dx와 dy 좌표에 있는 사과의 개수를 sum 변수에 추가 시킨다.
5. 큐에 append 시킨 개수만큼 pop을 시킨 뒤 다시 append를 반복하여 번수 L이 n//2와 같아지는 경우의 sum 값을 출력한다.

---

코드

from collections import deque

# 12, 3, 6, 9 시 방향
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

n = int(input())

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

# 채크할 배열
ch = [[0] * n for _ in range(n)]

# 총합
sum = 0

dQ = deque()
# 첫 root 노드 삽입 후, ch에 해당 위치 체크
# 그리고 sum 에 처음 root 노드 더하기
dQ.append((n//2, n//2))
ch[n//2][n//2] = 1
sum = sum + farm[n//2][n//2]

# L로 레벨 나타내기
L = 0

while True:
    # 도달 했을 경우!
    if L == n//2:
        print(sum)
        break

    size = len(dQ)

    # 큐 안에 들어있는 만큼 돌기
    # 언제 레벨을 올릴 것인지를 알기 위해서 위에 len의 큐를 통해서 해당 len 만큼 반복문을 돈다
    for i in range(size):
        tmp = dQ.popleft()

        # 4 방향 돌기
        # tmp 0은 행, tmp 1은 열
        for j in range(4):
            # 들렸던 곳인지 확인하기
            if ch[tmp[0]+dx[j]][tmp[1]+dy[j]] != 1:
                # 큐에 삽입
                dQ.append((tmp[0]+dx[j], tmp[1]+dy[j]))
                # 체크하기
                ch[tmp[0]+dx[j]][tmp[1]+dy[j]] = 1
                sum = sum + farm[tmp[0]+dx[j]][tmp[1]+dy[j]]
    
    # 다 돌았으면 레벨 올리기
    L = L + 1