[백준] 16236번 - 아기 상어 (파이썬)

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

# 아기 상어
import sys
from collections import deque
MAX = sys.maxsize
input = sys.stdin.readline
N = int(input())
arr = deque()
fish = []
now_x = 0
now_y = 0
for i in range(N):
    arr.append(list(map(int, input().split())))
    for j in range(N):
        if arr[i][j] != 0 and arr[i][j] != 9:
            fish.append((i, j))
        elif arr[i][j] == 9:
            now_x = i
            now_y = j
            arr[i][j] = 0
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
fish.sort()


def bfs():
    isEat = True
    big = 2
    eat_num = 0
    while isEat:
        if big == eat_num:
            big += 1
            eat_num = 0
        q = deque()
        q.append((now_x, now_y))
        time = [[MAX] * N for _ in range(N)]
        time[now_x][now_y] = 1
        while q:
            x, y = q.popleft()
            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]
                if 0 <= nx < N and 0 <= ny < N:
                    if time[nx][ny] == MAX and arr[nx][ny] <= big:
                        time[nx][ny] = time[x][y] + 1
                        q.append((nx, ny))
        eat_x = 0
        eat_y = 0
        minimum = MAX
        for x, y in fish:
            if arr[x][y] != 0 and arr[x][y] < big:
                if minimum > time[x][y]:
                    minimum = time[x][y]
                    eat_x = x
                    eat_y = y
        if minimum != MAX:
            eat(eat_x, eat_y, minimum)
            eat_num += 1
        else:
            isEat = False


def eat(x, y, len):
    global result
    global now_x
    global now_y
    result += (len-1)
    now_x = x
    now_y = y
    arr[x][y] = 0


result = 0
bfs()
print(result)

 

BFS

1. 처음에 배열을 입력 받을 때 0과 9가 아니면 fish리스트에 append해주고 9이면 현재 위치에 기록을하고 arr에서 9를 0으로 해준다.

2. 거리가 가까운 물고기가 많다면, 가장 위의 물고기 그것도 많다면 가장 왼쪽의 물고기를 먼저 먹어야 하므로 fish리스트를 sort한다.

3. 더이상 먹을 수 있는 물고기가 없을 때까지

  - q에 현재위치를 넣고 상하좌우를 돌면서 이동할 수 있는 곳들의 걸리는 시간리스트를 만든다(time)

  - fish 리스트에서 앞에서 부터 하나씩 검사하면서 시간리스트(time)이 가장 적은 값을 eat_x, eat_y에 기록

  - 물고기 먹기(eat): result에 해당 시간만큼 더해주고, 현재위치를 업데이트를 해준다음, arr를 0으로 초기화, eat++

  - 크기(big)와 먹은횟수(eat)가 같으면 big++, eat=0

 

더 쉽게 풀 수 있을 거 같지만 뭔가 더이상 건들기 싫은 문제였다.