16236-아기상어

www.acmicpc.net/problem/16236

1. 먹을 수 있는 물고기들의 위치와 거리 정보가 담긴 리스트 lst 를 만든다.

2. lst 를 거리순, x순, y순 으로 정렬한다.

3. lst 맨 앞에 있는 물고기를 먹고, 상어위치, 먹은 물고기수, 걸린시간, 물고기가 위치를 표시한 배열을 업데이트 해준다.

4. 물고기를 먹을만큼 먹었으면 크기를 업데이트 해준다.

5. 먹을 수 있는 물고기가 있을 때까지 반복한다.

6. 먹을 수 없는 물고기가 없으면 걸린 시간 출력

from collections import deque

# 너비 우선 탐색 ( 거리알아야 하니까 )
def bfs(y,x):
    global n,s_size,time
    visited[y][x] = True
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        # 인덱싱 범위 안에 있는 것만 q 에 넣자
        if 0 <= ny < n and 0 <= nx < n:
            q.append([ny, nx, time+1])
        # bfs 수행
    while q:
        now = q.pop(0)
        now_y = now[0]
        now_x = now[1]
        time = now[2]
        if not visited[now_y][now_x]:
            visited[now_y][now_x] = True
            # 지나갈 수 있는 곳이면
            if arr[now_y][now_x] == 0 or arr[now_y][now_x] == s_size:
                for i in range(4):
                    ny = now_y + dy[i]
                    nx = now_x + dx[i]
                    if 0 <= ny < n and 0 <= nx < n and not visited[ny][nx]:
                        q.append([ny, nx, time + 1])
            # 먹을 수 있는 상어가 있다면
            if 0 < arr[now_y][now_x] < s_size:
                lst.append([now_y,now_x,time])

n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]
s_size = 2

for i in range(n):
    for j in range(n):
        if arr[i][j] == 9:
            sy = i
            sx = j
            arr[i][j] = 0

dy = [-1,1,0,0]
dx = [0,0,1,-1]
visited = [[False for _ in range(n)]for __ in range(n)]
total = 0

lst = []
time = 0
q = []
bfs(sy,sx)

eat = 0
while len(lst):

    lst = sorted(lst, key=lambda x: x[1])
    lst = sorted(lst, key=lambda x: x[0])
    lst = sorted(lst, key=lambda x: x[2])

    sy = lst[0][0]
    sx = lst[0][1]
    total += lst[0][2]
    arr[sy][sx] = 0
    eat += 1
    if s_size == eat:
        s_size += 1
        eat = 0

    lst = []
    time = 0
    q = []
    visited = [[False for _ in range(n)] for __ in range(n)]
    bfs(sy,sx)

print(total)