[백준 16236번] 아기 상어

from collections import deque

n = int(input())

area = []
result = 0

shark_size = 2
ate_fish = 0

nx = [-1,1,0,0]
ny = [0,0,-1,1]

for i in range(n):
    area.append(list(map(int,input().split())))

for i in range(n):
    for j in range(n):
        if area[i][j] == 9:
            shark_location_x, shark_location_y = i, j


def bfs(x,y,sharkSize):
    visited = [[False]*n for _ in range(n)]
    distence = [[0]*n for _ in range(n)]

    visited[x][y] = True

    queue = deque([(x,y)])

    temp = []
    
    # 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. (bfs사용)
    while queue:
        prev_x, prev_y = queue.popleft()

        for i in range(4):
            next_x = prev_x + nx[i]
            next_y = prev_y + ny[i]

            if 0 <= next_x < n and 0 <= next_y < n and not visited[next_x][next_y]:
                if area[next_x][next_y] <= sharkSize:
                    visited[next_x][next_y] = True
                    distence[next_x][next_y] = distence[prev_x][prev_y] + 1
                    queue.append((next_x,next_y))
                    if area[next_x][next_y] < sharkSize and area[next_x][next_y] != 0:
                        temp.append((next_x,next_y,distence[next_x][next_y]))

    return sorted(temp,key=lambda x:(-x[2],-x[0],-x[1]))

while True:

    location_list = bfs(shark_location_x,shark_location_y,shark_size)

    # 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
    if len(location_list) == 0:
        break
    
    # 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
    # 정렬한 결과를 반영해준다.
    x, y, dis = location_list.pop()

    #움직이는 칸수가 곧 시간이 된다.
    result += dis
    area[shark_location_x][shark_location_y], area[x][y]  = 0, 0
    
    #상어좌표를 먹은 물고기 좌표로 옮겨준다.
    shark_location_x, shark_location_y = x, y

    ate_fish += 1

    if ate_fish == shark_size:
        shark_size += 1
        ate_fish = 0
    

print(result)

이번 문제는 아기 상어가 자신보다 크기가 작은 물고기만 잡아먹을 수 있다는 가정 하에, 거리가 가장 가까운 물고기부터 잡아먹었을 때 모든 물고기를 잡아먹는데 걸리는 시간을 구하는 문제이다.

 

생각보다 고려해야하는 조건이 많아서 조금 헷갈리기도 했고, 문제풀이의 흐름을 놓치는 바람에 제대로 풀이하지 못하였다.

 

하지만 중요한 것은 현재 위치에서 가장 가까운 위치, 즉 최단 거리에 존재하는 물고기를 찾기 위해 BFS를 사용해야 한다는 것과, '거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러 마리라면, 가장 왼쪽에 있는 물고기를 먹는다'는 조건을 만족시키기 위해 별도의 이동할 위치 정보들을 모아놓은 리스트를 선언한 후 lambda를 활용해 정렬해야한다는 것이다.

 

골드 이상의 문제들을 보면, 하나의 알고리즘만으로 풀리는 것이 아니기 때문에 문제의 조건과 흐름을 차근차근 읽고 풀이해야 한다는 것을 느낄 수 있었다 :)