[인프런 | BFS] 사과나무(BFS, 마름모)

사과나무(BFS)

현수의 농장은 N*N 격자판으로 이루어져 있으며, 각 격자안에는 한 그루의 사과나무가 심어저 있다. N의 크기는 항상 홀수이다. 가을이 되어 사과를 수확해야 하는데 현수는 격자판안의 사과를 수확할 때 다이아몬드 모양의 격자판만 수확하고 나머지 격자안의 사과는 새들을 위해서 남겨놓는다.
만약 N이 5이면 아래 그림과 같이 진한 부분의 사과를 수확한다.

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

▣ 입력설명
첫 줄에 자연수 N(홀수)이 주어진다.(3<=N<=20)
두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다.
이 자연수는 각 격자안에 있는 사과나무에 열린 사과의 개수이다.
각 격자안의 사과의 개수는 100을 넘지 않는다.

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

▣ 입력예제 1
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

▣ 출력예제 1
379

 

문제풀이

홀수개의 격자판에 마름모 모양으로 꽉 차게 방문한다.

 

문제해결

시작값을 정 중앙으로 시작하면서 하나씩 방문한다.

레벨을 따라서 가지를 뻗으면서 4개씩 방문

 

 

from collections import deque

def BFS(row, start_x, start_y) :
    dx = [-1, 0, 1, 0]                          #위 0, 오른 1, 아래쪽 2, 왼쪽 3
    dy = [0, 1, 0, -1]

    visite_list = [[False] * row for _ in range(row)]
    dq = deque()
    sum = 0

    #초기 방문 설정
    dq.append((start_x, start_y))
    visite_list[start_x][start_y] = True
    
    sum += map_data[start_x][start_y]               #방문한 맵의 값의 누적 합
    Level = 0                                       #마름모 퍼진 레벨

    while True : 
        if Level == (row//2) :                      #마름모가 끝까지 다 퍼진 경우 중단
            return sum

        size = len(dq)
        print(size)
        for i in range(size) :
            now_idx = dq.popleft()                  #큐에는 [(x, y)] 좌표 들어감
            print(now_idx)
            
            for d in range(4) :                     #4방향 방문
                next_x = now_idx[0] + dx[d]
                next_y = now_idx[1] + dy[d]
                
                if visite_list[next_x][next_y] == False:        #방문하지 않은곳만 방문
                    sum += map_data[next_x][next_y]             #방문한 맵의 값의 누적 합

                    visite_list[next_x][next_y] = True          #방문처리
                    dq.append((next_x, next_y))                 #다음 방문할 곳 큐에 넣기
        Level += 1
    print(sum)


# row = 5
# map_data = [[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]]

row = 9
map_data = [[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]]

print(BFS(row, (row//2), (row//2)))             #시작 좌표는 홀수의 정 중앙x, 중앙y