[BOJ] 16236. 아기상어(python)

📌문제

💪아이디어

1. 아기상어 위치구하기
   아기상어의 위치를 구하고 board에 있는 숫자 크기로 이동할 수있는지 체크할 때 혼동을 줄이기 위해 아기상어위치에 0을 대입한다.
   
   

2. 사이즈별 물고기 갯수
   먹을 수 있는 물고기가 남았는지 여부에 따라 이동하기 위해 사이즈별로 물고기의 숫자를 세어놓는다.
   
   

3. 가장 가까운 먹을 수 있는 물고기 위치
   
   • 이동하기
     보드의 값이 아기 상어의 사이즈 이하면 이동
     
     
   • 먹을 물고기 위치 체크
     0이 아니고 아기상어보다 작으면 먹을 수 있다.
     
     
   • 먹는 물고기 조건 체크
     먹을 수 있는 물고기의 아기상어가 움직인 거리, y좌표, x좌표를 heap에 넣는다. heappop하면 거리가 가장 가까운 -> 가장 위 -> 가장 왼쪽인 먹을 수 있는 물고기의 좌표를 얻을 수 있다.
     
     

   IndexError가 떠서 어려웠는데 이는 먹을 수 있는 물고리는 존재하지만 그 주위에 아기 상어보다 큰 물고기들 떄문에 이동할 수 없어 heap이 비어있는 상태일 때 발생했다. 그래서 heap이 비어있다면 None을 반환하도록 처리하였다.
   
   
   

4. 해당 위치 물고기 먹기
   먹을 수 있는 물고기 위치 체크해서 None이면 프로그램을 종료시켰다.
   값이 있으면 아기 상어가 이동한 거리만큼 시간초를 올리고 해당 위치의 물고기를 먹었으니 아기 상어가 물고기 먹은 수를 +1하고 board의 해당 위치를 0으로 바꾼다.
   
   

5. 아기상어 크기 체크
   아기상어가 먹은 물고기 수와 아기 상어 크기가 같으면 아기 상어가 크기 +1하고 먹은 수는 0으로 초기화시켜준다.
   아기 상어가 커졌으니 아기 상어크기 -1 사이즈의 물고기들을 먹을 수 있게 되어 먹을 수 있는 물고기 개수에 그만큼 더해준다. 물고기 사이즈는 1~6까지 있기 때문에 아기 상어 크기가 6이하일 경우에만 이 과정을 처리하게 한다.
   
   

🥂코드

import sys; input = sys.stdin.readline
from collections import deque
from heapq import heappush, heappop

class Baby:
    def __init__(self) -> None:
        self.y = 0
        self.x = 0
        self.size = 2
        self.eatCnt = 0

    def setLocation(self,y, x):
        self.y = y
        self.x = x

dy = (-1,0,1,0)
dx = (0,1,0,-1)

def findEatable():
    visited = [[False for _ in range(n)] for _ in range(n)]
    queue = deque()
    queue.append((baby.y,baby.x,0))
    visited[baby.y][baby.x] = True
    target = []

    while queue:
        y,x,dist = queue.popleft()
        if 0 < board[y][x] < baby.size:
            heappush(target,(dist,y,x))
            continue
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if 0 <= ny < n and 0 <= nx < n and not visited[ny][nx]:
                if board[ny][nx] <= baby.size:
                    visited[ny][nx] = True
                    queue.append((ny,nx,dist+1))
    if target: return heappop(target)
    return None

def eatFish(y,x):
    global eatableNum
    board[y][x] = 0
    eatableNum -= 1
    baby.eatCnt += 1
    baby.setLocation(y,x)

def sizeChk():
    global eatableNum
    if baby.eatCnt == baby.size:
        if baby.size <= 6: eatableNum += fishes[baby.size]
        baby.size += 1
        baby.eatCnt = 0

n = int(input())
board = []
baby = Baby()
fishes = dict().fromkeys(range(1,7),0)

for i in range(n):
    board.append(list(map(int,input().split())))
    for j in range(n):
        fishSize = board[i][j]
        if fishSize == 9: 
            baby.setLocation(i,j)
            board[i][j] = 0
        elif 0 < fishSize: 
            fishes[fishSize] += 1

clock = 0
eatableNum = 0
eatableNum += fishes[1]

while eatableNum:
    tmp = findEatable()
    if not tmp: break
    move, targetY, targetX = tmp
    eatFish(targetY,targetX)
    clock += move
    sizeChk()

print(clock)