백준 16236 아기상어

from collections import deque

n = int(input())
g = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(n):
    for j in range(n):
        if g[i][j] == 9:
            x, y = i, j
            g[i][j] = 0

def dfs(g, a, b, size):
    fishlist = []
    check = [[-1] * n for _ in range(n)]
    q = deque()
    q.append((a, b))
    check[a][b] = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            if check[nx][ny] == -1:
                if g[nx][ny] == 0 or g[nx][ny] == size:
                    check[nx][ny] = check[x][y] + 1
                    q.append((nx, ny))
                elif g[nx][ny] < size:
                    check[nx][ny] = check[x][y] + 1
                    fishlist.append((check[nx][ny], nx, ny))
                
    if not fishlist:
        return False
    else:
        fishlist.sort()
        return fishlist[0]

size = 2  
ans = 0
eatfish = 0
while True:
    t = dfs(g, x, y, size)
    if t != False:
        dist, now_x, now_y = t
        ans += dist
        g[now_x][now_y] = 0
        eatfish += 1
        if eatfish == size:
            size += 1
            eatfish = 0
        x, y = now_x, now_y
    else:
        print(ans)
        break

1. 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다. -> 이 조건을 안봄

시간 복잡도 계산