BOJ 16236 아기 상어

https://www.acmicpc.net/problem/16236
시간 2초, 메모리 512MB
input :

• N(2 ≤ N ≤ 20)
• N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9

output :

• 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력

조건 :

• 처음에 아기 상어의 크기는 2

• 1초에 상하좌우로 인접한 한 칸씩 이동

• 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다.
  (bfs에서 이동의 조건이 된다.)

• 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. (먹을 수 있는 물고기에 대한 조건)

• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.

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

• 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.

• 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

• 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

  자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가
  크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

  ---

조건이 너무 많은데 저 중에서 안 읽어서 문제가 된 부분은 가장 아래의 조건이였다.
일단 이동의 경우에는 자기보다 크기가 작으면 이동을 할 수 있다.

고로 visit 과 이 칸에 물고기가 존재한다면 자신보다 크기가 작은지 비교하자.

            if visit[nx][ny] == 0 and graph[nx][ny] <= baby_size:
                q.append((nx, ny, dis + 1))
                visit[nx][ny] = 1

그리고 각 bfs를 수행할 때 현재 위치에서 가장 가까운 곳에 위치한 먹이가 어디인지 찾는 것이 우리의 목표이다. 그리고 그걸 찾았으면은 bfs를 그만 두고 나와야 쓸 데 없는 탐색을 더 안 할 것이다.

                if graph[nx][ny] < baby_size and graph[nx][ny] != 0:
                    heappush(fish, (dis + 1, nx, ny))

이것을 heapq에다가 넣을 것인데 기본적으로 우선순위큐는 오름차순 순서대로 이것을 정렬한다.
이 이점을 살려서 (거리, x(높이), y(좌측)) 이러한 순으로 정렬이 되게 만들자.

그렇게 bfs를 한 번 수행하는 것 == 먹이를 1개 먹는 것
이기 때문에 cnt 변수의 수가 baby_size와 동일 해지면 크기를 키워주고 cnt를 초기화 해준다.

그리고 먹을 먹이 자체가 없다면 break를 걸어서 그만 어머니를 호출하도록 하자

ans = 0
cnt = 0
while True:
    a = bfs()
    cnt += 1
    if len(a) == 0:
        break

    dis, x, y = heappop(a)
    baby_x, baby_y = x, y
    if cnt == baby_size:
        cnt = 0
        baby_size += 1

    graph[x][y] = 0
    ans += dis

import sys
from heapq import heappop, heappush
from collections import deque


def bfs():
    fish = []
    q = deque([(baby_x, baby_y, 0)])
    visit = [[0] * n for i in range(n)]
    visit[baby_x][baby_y] = 1
    cnt = 0

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

        if cnt != dis:
            if len(fish) != 0:
                return fish
            cnt += 1

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if visit[nx][ny] == 0 and graph[nx][ny] <= baby_size:
                q.append((nx, ny, dis + 1))
                visit[nx][ny] = 1

                if graph[nx][ny] < baby_size and graph[nx][ny] != 0:
                    heappush(fish, (dis + 1, nx, ny))
    return fish


n = int(sys.stdin.readline())
graph = []
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]

baby_x, baby_y = 0, 0
baby_size = 2

for i in range(n):
    temp = list(map(int, sys.stdin.readline().split()))
    for j in range(n):
        if temp[j] == 9:
            baby_x, baby_y = i, j
            temp[j] = 0
    graph.append(temp)

ans = 0
cnt = 0
while True:
    a = bfs()
    cnt += 1
    if len(a) == 0:
        break

    dis, x, y = heappop(a)
    baby_x, baby_y = x, y
    if cnt == baby_size:
        cnt = 0
        baby_size += 1

    graph[x][y] = 0
    ans += dis

print(ans)

물론 그냥 튜플로 저장해서 정렬을 해도 되지만 한 번 써봤다 그냥.