사과나무 (BFS)

생성일: 2022년 2월 14일 오후 4:37

구현 코드 ⭐

# 사과나무 (BFS)
import sys
from collections import deque
#sys.stdin = open("input.txt", "rt")

def BFS():
    L = 0
    total = farm[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] # x좌표
                y = tmp[1]+dy[j] # y좌표
                if ch[x][y] == 0:
                    total += farm[x][y]
                    ch[x][y] = 1
                    Q.append((x,y))
        L += 1
    print(total)

if __name__ == "__main__":
    n = int(input())
    farm = []
    for _ in range(n):
        row = list(map(int, input().split()))
        farm.append(row)
    
    # 시계방향 좌표
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    ch = [[0 for _ in range(n)] for _ in range(n)]
    Q = deque()
    Q.append((n//2, n//2)) # 중앙부터 시작
    ch[n//2][n//2] = 1
    BFS()

• 격자판의 중앙 좌표부터 큐에 넣는다.
• dequeue를 해서 나온 좌표의 상하좌우 노드(좌표)를 큐에 다시 넣고 이를 반복한다.
• ch 배열을 통해 이미 검사한 노드인지 체크한다.
• 반복문이 끝나는 시점은 L(레벨)이 n//2일 때이다. ⇒ 예를 들어, n이 5라면 L이 2가될 때 반복문을 멈추면 다이아몬드 모양으로 격자판을 탐색하고 마칠 수 있다.