[백준] 16236번: 아기 상어

BFS 응용 문제이다. 상어의 크기가 점점 커지면서 매 탐색 시 탐색 조건이 바뀐다.

이 문제도 첫 시도를 실패했는데, 문제의 조건 중 '거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.' 를 구현할 때 착각한 것이 원인이었다.

BFS 탐색을 할 때 기준 좌표에서 위쪽, 왼쪽 순으로 이동 방향을 지정해주면 될 거라 생각했지만 (for dy, dx in [(-1, 0), (0, -1), ... ] 부분)
이 값은 탐색 중 이동하는 모든 블록 각각에 대해 적용되는 값이지, 처음 위치 기준이 아니기 때문에 처음 발견한 물고기가 같은 거리의 물고기들 중 가장 위쪽-왼쪽의 것임을 보장하지 않는다.

이 조건을 만족하기 위해서는 일단 먹을 수 있는 모든 물고기를 찾고, 그것들을 다시 한 번 거리-Y좌표-X좌표 순으로 정렬해야 한다.

import sys, copy
from collections import deque

input = sys.stdin.readline

N = int(input().rstrip())
matrix = []
coord_x, coord_y = 0, 0

for _ in range(N):
    arr = list(map(int, input().split()))
    if 9 in arr:
        coord_y, coord_x = (_, arr.index(9))
        arr[coord_x] = 0
    matrix.append(arr)


def find_food(init_y, init_x, size, count):
    q = deque([(init_y, init_x)])
    eatable = []
    visited = [[0] * N for _ in range(N)]

    while q:
        y, x = q.popleft()

        for dy, dx in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
            if (
                0 <= y + dy < N
                and 0 <= x + dx < N
                and visited[y + dy][x + dx] == 0
                and matrix[y + dy][x + dx] <= size
            ):
                if (matrix[y + dy][x + dx] == 0 or matrix[y + dy][x + dx] == size):
                    q.append((y + dy, x + dx))
                    visited[y + dy][x + dx] = visited[y][x] + 1
                elif 0 < matrix[y + dy][x + dx] < size:
                    visited[y + dy][x + dx] = visited[y][x] + 1
                    eatable.append((visited[y + dy][x + dx], y + dy, x + dx))

    if len(eatable) > 0:
        eatable.sort()
        c, y, x = eatable[0]
        matrix[y][x] = 0
        return (count + c, y, x)
    # 유효 범위 내에 먹이가 없을 때
    return (count, -1, -1)


stomach = 2
eat = 0
count = 0

while True:
    count, coord_y, coord_x = find_food(coord_y, coord_x, stomach, count)

    if coord_y > -1 and coord_x > -1:
        eat += 1
        if eat >= stomach:
            stomach += 1
            eat = 0
    else:
        break


print(count)