문제 - 생략
문제풀이
import sys
from collections import deque
sys.stdin=open("input.txt", "r")
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
Q=deque()
ch[n//2][n//2]=1 #최초 발자국을 표시한다.
sum+=a[n//2][n//2]
Q.append((n//2, n//2))
L=0 #L은 최상위 노드의 부모이면서 step의 출발점 이므로 0으로 세팅한다.
while True:
if L==n//2:
break
size=len(Q)
for i in range(size): #★ 레벨0일때 레벨1탐색을 마침, 레벨1 일때 레벨 2탐색을 마침
tmp=Q.popleft() #tmp에는 튜플 1개만 저장된다
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)
'파이썬 알고리즘 > DFS, BFS 활용' 카테고리의 다른 글
10.미로탐색(DFS) - 섹션6의 순열구하기 문제참고 (0) | 2022.11.11 |
---|---|
9.미로의 최단거리 통로(BFS) (1) | 2022.11.11 |
7. 송아지 찾기(BFS) (0) | 2022.11.10 |
6. 알파코드(DFS) (0) | 2022.11.10 |
5.동전 분배하기(DFS) (0) | 2022.11.09 |