- 문제 : https://www.acmicpc.net/problem/16236
Gold Level4 문제
삼성 기출 문제이고, 이전에 한 번 풀어본 적이 있는데, 그때는 너무 어려워서 답만 베끼고 넘겼었다
이번에도 스스로 풀지는 못했지만, 그래도 최대한 풀이를 이해해보려고 했다
며칠 뒤에 풀이 다시 한번 연습 해보려 한다
-정답 풀이 :
from collections import deque
sx,sy=0,0
shark_size=2
time=0
eat_cnt=0
fish_cnt=0
dx=[-1,1,0,0]
dy=[0,0,-1,1]
n=int(input())
data=[]
for i in range(n):
data.append(list(map(int,input().split())))
for j in range(n):
if 0<data[i][j]<=6:
fish_cnt+=1
if data[i][j]==9:
sx,sy=i,j
data[sx][sy]=0
def bfs(x,y):
q=deque()
#상어 x,y,이동한 거리
q.append((x,y,0))
visit=[[0]*n for _ in range(n)]
visit[x][y]=1
distance=[]
min_dist=10**9
while q:
x,y,dist=q.popleft()
for i in range(4):
nx,ny=x+dx[i],y+dy[i]
if 0<=nx<n and 0<=ny<n and not visit[nx][ny]:
#상어가 이동할 수 있는 위치인지 확인
if data[nx][ny] <=shark_size:
visit[nx][ny]=1
#먹을 수 있는 물고기가 있는 경우
#그 물고기 먹고 이동한 위치와 1칸 이동했으니 +1
if 0<data[nx][ny] < shark_size:
min_dist=dist
distance.append((dist+1,nx,ny))
#이동만 할 수 있는 경우
if dist+1 <= min_dist :
q.append((nx,ny,dist+1))
if distance:
distance.sort()
#가장 가까운 먹을 수 있는 물고기 위치 반환
return distance[0]
else:
return False
while fish_cnt:
result=bfs(sx,sy)
if not result:
break
sx,sy=result[1],result[2]
time+=result[0]
eat_cnt+=1
fish_cnt-=1
if shark_size == eat_cnt:
shark_size+=1
eat_cnt=0
data[sx][sy]=0
print(time)
- 풀이 이해 :
처음에 상어 위치, 물고기 갯수 세는 거는 이해했으므로 패스
현재 상어가 있는 위치에서부터 먹을 수 있는 가장 가까운 물고기의 위치를 찾는 탐색 로직이다.
def bfs(x,y):
q=deque()
#상어 x,y,이동한 거리
q.append((x,y,0))
visit=[[0]*n for _ in range(n)]
visit[x][y]=1
distance=[]
min_dist=10**9
while q:
x,y,dist=q.popleft()
for i in range(4):
nx,ny=x+dx[i],y+dy[i]
if 0<=nx<n and 0<=ny<n and not visit[nx][ny]:
#상어가 이동할 수 있는 위치인지 확인
if data[nx][ny] <=shark_size:
visit[nx][ny]=1
#먹을 수 있는 물고기가 있는 경우
#그 물고기 먹고 이동한 위치와 1칸 이동했으니 +1
if 0<data[nx][ny] < shark_size:
min_dist=dist
distance.append((dist+1,nx,ny))
#이동만 할 수 있는 경우
if dist+1 <= min_dist :
q.append((nx,ny,dist+1))
if distance:
distance.sort()
#가장 가까운 먹을 수 있는 물고기 위치 반환
return distance[0]
else:
return False
먹을 수 있는 물고기가 있을 때까지 루프를 돌린다.
bfs로 현재 상어가 있는 위치에서 먹을 수 있는 가장 가까운 물고기의 위치와 거기까지의 거리를 받는다
sx,sy까지의 거리가 곧 가는데 걸리는 시간이므로 dist(result[0])을 time에 더해주고, 먹은 물고기 +1, 물고기 갯수 -1 을 해준다
이부분이 잘 이해가 가지 않는데, 먹은 물고기 개수와 상어의 크기가 같으면 상어의 크기를 +1 한다???
if shark_size == eat_cnt:
shark_size+=1
eat_cnt=0
while fish_cnt:
result=bfs(sx,sy)
if not result:
break
sx,sy=result[1],result[2]
time+=result[0]
eat_cnt+=1
fish_cnt-=1
if shark_size == eat_cnt:
shark_size+=1
eat_cnt=0
data[sx][sy]=0
print(time)
'백준 > Search' 카테고리의 다른 글
[bfs/백준] 1707번 : 이분 그래프 (0) | 2022.07.28 |
---|---|
[bfs/백준] 1389번 : 케빈 베이컨의 6단계 법칙 (0) | 2022.07.28 |
[dfs/백준] 11725번 : 트리의 부모 찾기 (0) | 2022.07.26 |
[bfs/백준] 10026번 : 적록색약 (0) | 2022.07.24 |
[bfs/백준] 7569번 : 토마토 (0) | 2022.07.24 |