[코딩인터뷰] 백준 16236번

백준 16236번

from collections import deque

# 크면 못지나감. 같으면 지나감. 작아야 먹음
# 자기 크기만큼 먹어야 성장
n = int(input())
space = []
for _ in range(n):
    space.append(list(map(int, input().split())))

# 아기상어 처음 위치
shark_loc = (0, 0)
for i in range(n):
    for j in range(n):
        if space[i][j] == 9:
            space[i][j] = 0
            shark_loc = (i, j)

# 아기 상어 처음 크기
shark_level = 2
shark_eat_count = 0
# 시간
time = 0
# 이동
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

while True:
    q = deque()
    q.append((shark_loc[0], shark_loc[1], 0))
    v = [[False] * n for _ in range(n)]
    v[shark_loc[0]][shark_loc[1]] = True
    # 먹을 거 탐색
    targets = []
    while 0 < len(q):
        cx, cy, cd = q.popleft()

        if 0 < space[cx][cy] < shark_level:
            targets.append((cx, cy, cd))

        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            nd = cd + 1
            if 0 <= nx < n and 0 <= ny < n and not v[nx][ny] and space[nx][ny] <= shark_level:
                q.append((nx, ny, nd))
                v[nx][ny] = True

    # 먹을 거 없으면 도움
    if len(targets) == 0:
        is_continue = False
        break
    # 먹을 거 선택
    target = (n, n, 10**10)
    for i in range(len(targets)):
        if  targets[i][2] < target[2]:
            target = targets[i]
        elif targets[i][2] == target[2]:
            if targets[i][0] < target[0]:
                target = targets[i]
            elif targets[i][0] == target[0]:
                if targets[i][1] < target[1]:
                    target = targets[i]
    # 먹는다
    shark_loc = (target[0], target[1])
    time += target[2]
    space[shark_loc[0]][shark_loc[1]] = 0
    shark_eat_count += 1
    if shark_eat_count == shark_level:
        shark_level += 1
        shark_eat_count = 0

print(time)