Algorithm - 사과나무(BFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[사과나무(BFS)]

 

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

(단, N은 항상 홀수)

 

가을이 되어 사과를 수확해야 하는데, 현수는 격자판 안의 사과를 수확할 때 다이아몬드 모양의 격자판만 수확하고 나머지 격자 안의 사과는 새들을 위해서 남겨놓는다. 만약, N이 5이면 아래 그림과 같이 진한 부분의 사과를 수확한다.

 

5*5 격자판

 

현수가 수확하는 사과의 총 개수를 출력하는 프로그램을 작성하시오.

 

 

*입력 설명

첫 번째 줄에 자연수 N(3 ≤ N ≤ 20, 홀수)이 주어진다.

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

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

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

 

*출력 설명

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

 

 

---

 

 

풀이(Python)

답안

import sys
from collections import deque
sys.stdin = open('AA/input_63.txt', 'rt')

dx =[-1, 0, 1, 0]
dy = [0, 1, 0, -1]
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ch = [[0] * n for _ in range(n)]
sum = 0
L = 0

Q = deque()
ch[n//2][n//2] = 1
sum += a[n//2][n//2]
Q.append((n//2, n//2))


while True:
    if L == n//2:
        break
    size = len(Q)
    for i in range(size):
        tmp = Q.popleft()
        for j in range(4):
            x = tmp[0] + dx[j]
            y = tmp[1] + dy[j]
            if ch[x][y] == 0:
                sum += a[x][y]
                ch[x][y] = 1
                Q.append((x, y))
    L += 1
print(sum)

# 출력 : 379

 

input_63.txt(입력)

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. 넓이우선탐색은 큐 자료구조를 활용한다.
2. 격자판의 정 중앙(" a[n//2][n//2] ")을 기준으로 상하좌우 탐색을 시작한다.
3. 단, 상하좌우는 " 좌 -> 상 -> 우 -> 하 " 순으로 시계방향 탐색을 한다.
4. 상태트리의 레벨이 증가하면서 동시에 상하좌우 탐색을 지속한다. (단, 이미 방문한 격자는 제외함 : 중복제거)
5. 이러한 탐색 방법을 사용하면 결국 N*N 격자판에서 다이아몬드 모양의 격자만을 탐색할 수 있다.
6. 참고로, 상하좌우 탐색이기 때문에 노드에서 뻗어나오는 간선의 개수는 4개로 항상 동일하다.
7. 변수 dx, dy는 상하좌우 탐색을 하기 위해 사용되는 리스트이다.
8. 변수 ch는 재방문을 방지하기 위해 사용되는 리스트이다. (중복 체크)
9. 변수 sum에 다이아몬드 형태로 격자판의 값을 모두 더해서 저장한다.
10. 격자판의 중앙지점을 나타내는 코드는 a[n//2][n//2] 이다. (탐색의 시작점)
11. 상태트리의 레벨(L)이 n//2일 때, 넓이우선탐색이 종료된다.
12. 상태트리의 레벨(L)이 0이면 size의 크기는 1이고, 레벨이 1이면 size의 크기는 4가 되며, 레벨이 2이면 size의 크기는 16이 된다.