274. 아기상어

백준

1. Python

참고

import sys
from collections import deque
input = sys.stdin.readline

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

sx, sy = 0, 0

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

            
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

size = 2
move = 0
eat = 0

while True:
    q = deque()
    q.append((sx, sy, 0))
    visit = [[0] * n for _ in range(n)]
    flag = 1e9
    fish = []
    while q:
        x, y, count = q.popleft()

        if count > flag: #먹을 수 있는 상어를 찾은 횟수까지만 탐색을 수행
            break

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] <= size and not visit[nx][ny]:
                if board[nx][ny] != 0 and board[nx][ny] < size:
                    fish.append((nx, ny, count + 1))
                    flag = count
                visit[nx][ny] = 1
                q.append((nx, ny, count + 1))

    if len(fish) > 0:
        fish.sort() #맨위 왼쪽 맨 끝에 위치한 물고기를 먼저 먹는다는 것은 (세로, 가로) 순서로 오름차순 정렬 하라는 뜻
        x, y, m = fish[0][0], fish[0][1], fish[0][2]
        move += m
        eat += 1
        board[x][y] = 0
        if eat == size:
            size += 1
            eat = 0
        sx, sy = x, y
    else:
        break

print(move)