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

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

16236번: 아기 상어

처음에는 주어진 조건대로 구현해서 2중 for문으로 먹을 수 있는 물고기가 있는지 찾은 다음에 있으면 bfs를 실행하고 없으면 시간을 출력하게 했더니 런타임 에러가 발생했다.

 

그리고 가장 위, 가장 왼쪽에 있는 물고기를 먹기위해 dx, dy에 순서를 주면 된다고 생각했지만 4번 예제 처럼 (0,3) 물고기를 먹었을 때 다음에는 (0,4)를 먹어야 하는데 (1,1)을 먹는 문제가 발생한다. 그래서 4~5번 과정으로 구현

 

1. 아기 상어의 좌표를 저장하고 0으로 초기화한다

2. 아기 상어 좌표, 무게, 이동 시간, 먹은 횟수를 bfs에 입력할 변수로 사용하고 초기화한다

3. 다음 칸이 0이거나 무게와 같은 칸이면 이동한다

4. 0과 아기 상어의 무게 사이라면 바로 먹지 않고 먹을 수 있는 물고기를 저장하는 can_eat에 저장

5. 먹을 수 있는 물고기가 있으면 그 중 최소값을 먹는다. 그래야 조건대로 가장 위, 가장 왼쪽에 있는 물고기를 먹는다

6. bfs 결과 더 이상 먹을게 없다면 입력한 시간을 출력

from collections import deque
import sys

input = sys.stdin.readline
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

def bfs(x, y, weight, time, eat):
    q, can_eat = deque(), []
    q.append([x, y])
    c = [[-1]*n for _ in range(n)]
    c[x][y] = time
    while q:
        qlen = len(q)
        while qlen:
            x, y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < n:
                    if c[nx][ny] == -1:
                        if a[nx][ny] == 0 or a[nx][ny] == weight:
                            c[nx][ny] = c[x][y] + 1
                            q.append([nx, ny])
                        elif 0 < a[nx][ny] < weight:
                            can_eat.append([nx, ny])
            qlen -= 1

        if can_eat:
            nx, ny = min(can_eat)
            eat += 1
            if eat == weight:
                eat = 0
                weight += 1
            a[nx][ny] = 0
            return nx, ny, weight, c[x][y] + 1, eat

    print(time)
    sys.exit()

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

for i in range(n):
    for j in range(n):
        if a[i][j] == 9:
            x, y = i, j
            a[i][j] = 0

weight, time, eat = 2, 0, 0
while True:
    x, y, weight, time, eat = bfs(x, y, weight, time, eat)