[백준]16236번 아기 상어(python 파이썬)

(https://www.acmicpc.net/problem/16236

16236번: 아기 상어

아기 상어 / 골드 3 / 180분

사용 알고리즘 : bfs

 

 

 

 

생각해보아야 할 것

 

1. 먹이 찾기

거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러 마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

- 먹이를 발견 하더라도 가장 위, 왼쪽의 물고기를 가져와야 하므로 해당 거리에 해당되는 먹이를 모두 가져온다.

- 먹이를 발견 한 경우 더 이상 큐에 추가시키지 않는다. ( 거리가 더 길기 때문)

 

 

먹이를 처음 발견 한 경우

• 먹이flag(feed_yet) False 할당
• 먹이 리스트에 해당 x,y,길이 추가

if not visited[nx][ny] and G[nx][ny]<=fish_size:
    visited[nx][ny] = True
    if 0<G[nx][ny]<fish_size:
        feed_yet = False
        feed_list.append((nx,ny,t+1))

먹이를 전에 발견 한 경우

• 먹이를 발견하였으므로 그 보다 긴 거리를 탐색할 필요가 없음

if feed_yet:
    Q.append((nx,ny,t+1))

 

 

2. 최소 거리의 먹이 찾기가 끝난 후

먹이 및 물고기 업데이트

• 가장 가까운 거리 중 가장 위쪽, 가장 왼쪽 먹이를 가져오기 위하여 정렬

feed_list.sort(key= lambda x:(-x[2],-x[0],-x[1])) # 길이,i,j순으로 sort

 

• 해당 먹이를 가져옴

fx,fy,ft = feed_list[-1]

 

• 그래프 업데이트
  • 먹이의 위치 물고기(9)로 할당
  • 기존의 물고기 위치는 0으로 할당
  • 물고기 위치 업데이트

G[fish_x][fish_y] = 0
G[fx][fy]=9
fish_x,fish_y = fx,fy

 

• 다시 bfs을 돌리기 위하여 visited 리스트 초기화

visited = [[False for _ in range(N)] for _ in range(N)]
visited[fx][fy] =True
Q.append((fx,fy,0))
feed_yet = True
feed_list = []
feed_dist = sys.maxsize

물고기 크기 증가

• 물고기 카운트 증가
• 만약 물고기 먹이 카운트가 사이즈와 같은 경우
  • 물고기 사이즈 증가, 물고기 카운트 0 초기화

fish_cnt+=1
if fish_size == fish_cnt:
    fish_cnt=0
    fish_size+=1

 

 

전체 코드 

import sys
input = sys.stdin.readline
from collections import deque

N = int(input())
G = [list(map(int,input().split())) for _ in range(N)]
X = [-1,1,0,0]
Y = [0,0,-1,1]
Q = deque()
for i in range(N):
    for j in range(N):
        if G[i][j] == 9:
            fish_x = i
            fish_y = j
            Q.append((i,j,0))
visited = [[False for _ in range(N)] for _ in range(N)]
fish_size = 2
fish_cnt = 0

result = 0

feed_yet = True
feed_dist = sys.maxsize
feed_list = []
while Q:
    x,y,t = Q.popleft()
    # if t == feed_dist:
    #     break

    for dx,dy in zip(X,Y):
        nx,ny = x+dx,y+dy
        if 0<=nx<N and 0<=ny<N :
            if not visited[nx][ny] and G[nx][ny]<=fish_size:
                visited[nx][ny] = True
                if 0<G[nx][ny]<fish_size:
                    feed_dist +=1
                    feed_yet = False
                    feed_list.append((nx,ny,t+1))
                if feed_yet:
                    Q.append((nx,ny,t+1))
                    
    if not Q:
        if feed_list:
            feed_list.sort(key= lambda x:(-x[2],-x[0],-x[1])) # 길이,i,j순으로 sort
            fx,fy,ft = feed_list[-1]
            fish_cnt+=1
            result+=ft
            if fish_size == fish_cnt:
                fish_cnt=0
                fish_size+=1
            # 그래프 update
            G[fish_x][fish_y] = 0
            G[fx][fy]=9
            fish_x,fish_y = fx,fy
            visited = [[False for _ in range(N)] for _ in range(N)]
            visited[fx][fy] =True
            Q.append((fx,fy,0))
            feed_yet = True
            feed_list = []
            feed_dist = sys.maxsize
                
print(result)

 

실행 결과

 

저는 이 문제를 해결하는데 3시간 넘게 걸렸던 것 같습니다. ㅠㅠ

 

문제를 정확히 읽어야 푸는 시간이 줄어드므로 정확히 읽는 습관을 들여야 겠습니다.