문제 설명

먼저 이 문제는 삼성전자 기출 문제로 난이도가 나름 있었다.
문제를 간단히 설명 하면

1. 상어는 물고기를 먹으며 몸집이 커지고 최대한 물고기를 많이 먹어야한다.

2. 그때 최단 거리로 물고리를 다 먹어야한다

해결 방법

먼저 문제가 긴만큼 그대로 따라가면 되었다. 각 상어의 크기마다 가장 가까운 거리를 선택하면 되는 그리디 알고리즘으로 해결 할 수있었고,
디테일한 조건은 문제에서 확인 할 수있었다.

해답 코드

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

N = int(input().rstrip())
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

def get_destination(size, matrix, shark):
  #현재 상어 위치와 크기로 조건에맞는 목적위치 리턴 함수
  #먹을 수 있는 물고기가 없다면 (-1,-1)리턴
  cnd = []
  for i in range(N):
    for j in range(N):
      if matrix[i][j] < size and matrix[i][j] > 0:
        c = get_cost(size, matrix, shark, (i,j))
        if c != False:
          heapq.heappush(cnd, (c, i, j))
  #먹을수 있는 물고기가 한마리인 경우
  if not cnd:
    return ((-1,-1,-1))
  else:
    res = heapq.heappop(cnd)
    return res
def get_cost(size, matrix, s, d):
  #매개변수로 받은 위치 두개에 따른 거리값 출력
  q = deque()
  visit = [[0] * N for _ in range(N)]
  q.append((s[0], s[1], 0))
  while q:
    curY, curX, cost = q.popleft()
    for i in range(4):
      newY = curY + dy[i]
      newX = curX + dx[i]
      #맵밖을 벗어나지 않고
      if newY >= 0 and newY < N and newX < N and newX >= 0:
        #size이하의 물고기가 있을 때 이동가능
        if matrix[newY][newX] <= size and visit[newY][newX] == 0:
          if newY == d[0] and newX == d[1]:
            return cost+1
          else:
            q.append((newY, newX, cost+1))
            visit[newY][newX] = 1
          
  return False

#N X N크기의 맵 입력
matrix = []
for _ in range(N):
  matrix.append(list(map(int, input().split())))
#상어 위치 찾기
for i in range(N):
  for j in range(N):
    if matrix[i][j] == 9:
      start = (i,j)
      matrix[i][j] = 0
      break
size = 2
result = 0
count = 0
while True:
  #먹을 목적지 위치 찾기
  cost, y, x = get_destination(size, matrix, start)
  dest = (y,x)
  # print(dest, '로 이동!!!')
  #더이상 먹을 수 있는 물고기가 없다면 반복문 종료
  if dest[0] == -1:
    break
  #이동할 거리 비용구하기
  result += cost
  #거리 이동시켜 주기
  start = dest
  #물고기 먹은양 count
  count +=1
  if count == size:
    count = 0
    size += 1
  #먹은 물고기 없애주기
  matrix[dest[0]][dest[1]] = 0
  # print('-------------------')
  # for i in range(N):
  #   for j in range(N):
  #     print(matrix[i][j], end = "|")
  #   print()
print(result)

걸린시간

해매는 시간이 특별히 없었지만 순식간에 1시간 넘는 시간이 흘렀다
핵심적으로는 BFS로 거리를 구할때 visit리스트를 만들지 않고 그냥 구현해버려서 거기서 10분정도를 애먹었던것 같다!!!