백준 16236 아기상어

import sys
from collections import deque

n = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for i in range(n)]

dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]

shark_queue = deque()

current_size = 2
level = 0
total_result = 0


def shark_BFS():
    while shark_queue:
        x, y = shark_queue.popleft()
        visited[x][y] = 1

        for i in range(4):
            dx = x + dir[i][0]
            dy = y + dir[i][1]

            if dx < 0 or dx >= n or dy < 0 or dy >= n:
                continue

            if graph[dx][dy] <= current_size and visited[dx][dy] == 0:
                visited[dx][dy] = 1
                dir_cost[dx][dy] = dir_cost[x][y] + 1
                shark_queue.append((dx, dy))

                if graph[dx][dy] != 0 and graph[dx][dy] < current_size:
                    shark_eat.append((dir_cost[dx][dy], dx, dy))


for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            graph[i][j] = 0
            shark_queue.append((i, j))

while True:
    shark_eat = list()
    visited = [[0 for i in range(n)] for i in range(n)]
    dir_cost = [[0 for i in range(n)] for i in range(n)]

    shark_BFS()

    if shark_eat:
        shark_eat.sort()
        shark_queue.append((shark_eat[0][1], shark_eat[0][2]))
        graph[shark_eat[0][1]][shark_eat[0][2]] = 0
        total_result += shark_eat[0][0]
        level += 1

        if current_size == level:
            current_size += 1
            level = 0

    else:
        print(total_result)
        break

링크텍스트

최근 푼 문제중 가장 재밌게 푼 문제가 아닌가 싶다. 문제 설명을 하기보단 어떻게 풀었는지 설명해보겠습니다.

일단 현재 위치에서 자기보다 작거나 같은 곳은 갈수있는데, 갈수있는 위치중 자신의 크기보다 작은 애들은 먹을수있다.

먹으면 level 이 1 이 상승해 만약 현재 크기가 2 라면 2개를먹어야 3이된다. 3이면 3개를 먹어야 4가 되는 느낌.

​

하여튼 BFS 로 갈수있는 방향의 시간을 각각 남겨주고 먹을수 있는 고기중 cost가 같다면 거리,x,y 축으로 정렬을 한후 젤 앞 고기 부터 먹게했다.

그렇게 먹으면서 커지다가 더이상 먹을수있는 고기가 없어지면 break 를 걸어 지금까지 먹은 거리들을 표시해준다.

​