.PNG)
62. 사과나무(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
<내 풀이>
내가 생각했던 방법은 챕터2에서 했던 것처럼 줄별로 하는 방식이었다
그러나 그걸 bfs로 어떻게 구현할 지를 알 수 없어서 결국 포기하고 말았음
(그런데 해답은 전혀 그쪽이 아니었다 BFS쪽이었으니)
<풀이>
- 가운데에서 상,하,좌,우로 돌면서 탐색하는 방식을 취함
- 한번 간 곳은 가면 안됨, 이미 칠해져있으니깐 => ch만들어서 체크해주기
from collections import deque
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)]
ch[n//2][n//2]=1
sum=0
sum+=a[n//2][n//2]
q=deque()
q.append((n//2,n//2))
#k[0]이 앞의 값 k[1]이 뒤의 값
level=0
while True :
if level==n//2:
break
size=len(q)
for i in range(size) :
k=q.popleft()
for j in range(4):
x=k[0]+dx[j]
y=k[1]+dy[j]
if ch[x][y]==0:
sum+=a[x][y]
ch[x][y]=1
q.append((x,y))
level+=1
print(sum)
어떤 방식으로 진행되냐면
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)]
ch[n//2][n//2]=1
sum=0
sum+=a[n//2][n//2]
q=deque()
q.append((n//2,n//2))
#k[0]이 앞의 값 k[1]이 뒤의 값
level=0
while True :
if level==n//2:
break
size=len(q)
for i in range(size) :
k=q.popleft()
for j in range(4):
x=k[0]+dx[j]
y=k[1]+dy[j]
if ch[x][y]==0:
sum+=a[x][y]
ch[x][y]=1
q.append((x,y))
print(level, size) #요 print 부분을 통해 어떻게 진행되고 있는지 살펴보자면
for i in ch :
print(i)
level+=1
==>
0 1
[0, 0, 0, 0, 0][0, 0, 1, 0, 0]
[0, 1, 1, 1, 0][0, 0, 1, 0, 0]
[0, 0, 0, 0, 0]
1 4 (레벨이 1증가하고 사이즈는 4)
[0, 0, 1, 0, 0][0, 1, 1, 1, 0]
[1, 1, 1, 1, 1][0, 1, 1, 1, 0]
[0, 0, 1, 0, 0]
라고 출력이 됨
<반성점>
-
2차 리스트 한번에 읽는 법을 까먹었음
a=[list(map(int, input().split())) for _ in range(n)] -
2단계에서 했던 상하좌우 풀이법을 까먹었음
d[x]=[-1,0,1,0]
d[y]=[0,1,0,-1]
===>
x=k[0]+dx[j]
y=k[1]+dy[j] -
여전히 BFS탐색 방법이 낯설다. 익숙해지는 게 답이다
<배운 점>
- ch=[[0]*n for _ in range(n)]
=>nxn 만큼 0리스트들을 만드는 것 - q.append(n//2,n//2)
=> 이렇게 받으면 2 argument를 받은 것으로 인식이 되어서 error
==> 괄호 하나 더 덮어줘서 튜플 하나로 받아줘야 한다. 그리고 나중에 따로 값을 입힐 때 [0],[1]과 같이 분리해주면 됨
q.append((n//2,n//2))
<2차 내 풀이>
- 역시나 이번에도 빼먹은 부분들이 아주 많았음, 강의 대충 듣고 복습 안한 것이 티가 난다
빼먹은 부분 :
- 총 n//2만큼만 돌려져야 한다
- q안에 있는 것을 다 처리할 때를 한번으로 간주하는 것
- 한번 돌 때 Q안에 있는 애들이 한번에 돌려져야 하므로 Q의 길이만큼 돌아야 한다
size=len(q)
for j in range(size) :
k=q.popleft()
from collections import deque
n=int(input()) #항상 홀수로
a=[list(map(int,input().split())) for _ in range(n)]
ch=[[0]*(n+1) for _ in range(n+1)]
q=deque()
dx=[-1,0,1,0]
dy=[0,1,0,-1]
q.append((n//2,n//2))
ch[n//2][n//2] = a[n//2][n//2]
while q :
k=q.popleft()
for i in range(4) :
x=k[0]+dx[i]
y=k[1]+dy[i]
if 0<=x<=n and 0<=y<=n and ch[x][y]==0:
ch[x][y]=a[x][y]
q.append((x,y))
s=0
for i in ch :
print(i)
s+=sum(i)
print(s)
=> 풀이 보고 오답하고 수정
from collections import deque
n=int(input()) #항상 홀수로
a=[list(map(int,input().split())) for _ in range(n)]
ch=[[0]*(n+1) for _ in range(n+1)]
q=deque()
dx=[-1,0,1,0]
dy=[0,1,0,-1]
level=0
q.append((n//2,n//2))
ch[n//2][n//2] = a[n//2][n//2]
while True :
if level==n//2: #N의 절반만큼만 시행돼야 한다
break
size=len(q) #한번 돌 때 Q안에 있는 애들이 한번에 돌려져야 하므로 Q의 길이만큼 돌아야 한다
for j in range(size) :
k=q.popleft()
for i in range(4) :
x=k[0]+dx[i]
y=k[1]+dy[i]
if ch[x][y]==0:
ch[x][y]=a[x][y]
q.append((x,y))
level+=1 #q가 한번 시행되고 난 후에야 한번 도는게 끝난거니 이제야 level을 더해준다
s=0
for i in ch :
s+=sum(i)
print(s)
