[백준 문제풀이] 얼렁뚱땅 16236 아기상어 풀이

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

16236번: 아기 상어

 

티스토리 복구 되어꾸나 ><

올만이야 반가오

 

from collections import deque
import sys

dx = [0,0,1,-1]
dy = [1,-1,0,0]
def search_mamma(tx,ty,size) :
    global arr
    global ok_list
    q = deque()
    q.append([tx,ty,0])
    global min_mamma
    while q :
        x,y,count = q.popleft()
        for i in range(4) :
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<n :
                if visited[nx][ny] == 0 and arr[nx][ny] <= size :
                    visited[nx][ny] = 1
                    if arr[nx][ny] == 0 or arr[nx][ny] == size:
                        q.append([nx,ny,count+1])
                    elif arr[nx][ny] < size :
                        if count + 1 <= min_mamma :
                            min_mamma = count+1
                            q.append([nx,ny,count+1])
                            ok_list.append([nx,ny])


arr = []
n = int(input())
baby = []

for i in range(n) :
    tmp = list(map(int,input().split()))
    arr.append(tmp)
    if 9 in tmp :
        baby = [i, tmp.index(9)]
        
arr[baby[0]][baby[1]] = 0
si = 2
all_time = 0
eat_time = 0
while True :
    visited = [[0]*n for _ in range(n)]
    visited[baby[0]][baby[1]] = 1
    ok_list = []
    min_mamma = n*n+1
    search_mamma(baby[0],baby[1],si)
    if len(ok_list) == 0 :
        print(all_time)
        sys.exit()
    all_time += min_mamma
    ok_list.sort(key=lambda x:(x[0],x[1]))
    baby = ok_list[0]
    arr[baby[0]][baby[1]] = 0
    eat_time += 1
    if eat_time == si :
        si += 1
        eat_time = 0