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

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

16236번: 아기 상어

• 이 문제를 처음 읽고 든 생각은 아래와 같습니다.
  • BFS로 구현을 하고, 거리를 담을 리스트가 하나 더 있어야 한다
  • 요즘 알고리즘 풀 때 하는 생각 : 주어진 조건대로 차근차근 생각하자
• 먼저, BFS 함수 안에 들어갈 input 값들에는 상어의 좌표와, 상어의 크기가 들어가야 합니다.간단하게 상어의 위치만 파악할 수 있는 2중 for문을 돌려서 상어의 좌표를 x, y에 저장해주고 상어의 크기는 2로 초기화 한 뒤, 시작해주면 됩니다.
• 일반적인 최단거리를 구하기 위한 BFS 형식과 거의 동일하고, 가장 중요한 부분은 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러 마리라면, 가장 왼쪽에 있는 물고기를 먹는다. 의 조건을 만족시켜주기 위해 어떤 좌표의 물고기를 먹을지를 return 해줘야 합니다. 여기서 사용한 구현 방법은 temp에 담긴 좌표를 각각 조건의 순서에 따라 정렬을 해줬습니다.
• 그다음으로는 먹을 수 있는 물고기가 없을 때까지 while문을 돌려주면서, BFS 함수의 return 값을 받아온 뒤, 받아온 값들 중 거리 값을 result에 더해주면서 시간을 계산해주고, return 값들 중 먹은 물고기의 좌표가 담긴 nx, ny를 다음 BFS함수의 input값으로 넣어주기 위해 초기화시켜줍니다.
• while문 마지막에는 상어가 자신과 size 만큼의 물고기를 먹어야 사이즈가 증가하므로 해당 내용을 구현해줍니다.

import sys
from collections import deque

input = sys.stdin.readline

# 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
# 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.

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


dx = [0,0,1,-1]
dy = [1,-1,0,0]
cnt = 0
x,y,size = 0,0,2
#상어위치
for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            x = i
            y = j

def biteFish(x,y,shark_size):
    distance = [[0] * n for _ in range(n)]
    visited = [[0] * n for _ in range(n)]
    # 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. (bfs사용)
    q = deque()
    q.append((x,y))
    visited[x][y] = 1
    temp = []
    while q:
        cur_x,cur_y = q.popleft()
        for i in range(4):
            nx = cur_x + dx[i]
            ny = cur_y + dy[i]
            if 0<= nx < n and 0<= ny < n and visited[nx][ny] == 0:
                if graph[nx][ny] <= shark_size:
                    q.append((nx,ny))
                    visited[nx][ny] = 1
                    distance[nx][ny] = distance[cur_x][cur_y] + 1
                    if graph[nx][ny] < shark_size and graph[nx][ny] != 0:
                        temp.append((nx,ny,distance[nx][ny]))

# 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
    return sorted(temp,key=lambda x: (-x[2],-x[0],-x[1]))


cnt = 0
result = 0
while 1:
    shark = biteFish(x,y,size)
    # 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
    if len(shark) == 0:
        break
    # 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
    # 정렬한 결과를 반영해준다.
    nx,ny,dist =shark.pop()
    
    #움직이는 칸수가 곧 시간이 된다.
    result += dist
    graph[x][y],graph[nx][ny] = 0,0
    #상어좌표를 먹은 물고기 좌표로 옮겨준다.
    x,y = nx,ny
    cnt += 1
    if cnt == size:
        size += 1
        cnt = 0
print(result)