[백준] 16236번 아기 상어 (Python)

백준 16236 아기 상어

BFS를 활용해 구현하는 문제였다. 여러 가지 조건을 따지며 탐색하는 문제였는데 여러 가지 조건을 따지다 보니 실수한 부분이 많아 정리하려고 한다. 이 문제의 포인트는 다음과 같다.

1. BFS 탐색을 통하여 가장 가까운 "먹을 수 있는" 물고기를 찾는다.
2. 해당하는 물고기가 2마리 이상이면 조건을 따져 어떤 물고기를 먹을 것인지 결정한다.

• 가장 위에 있는 물고기 -> 같은 높이라면 더 왼쪽에 있는 물고기 선택.

3. 물고기를 먹게 되면 상어의 위치, 시간, 먹은 물고기 개수 업데이트하고 물고기를 제거한다.
4. 이 과정을 반복한다.

내가 실수한 부분이다.

1. 처음에 상어를 입력받은 자리를 0으로 바꾸어 주지 않다 물고기로 인식했다.
   2. dy, dx만 잘 설정하면 물고기가 더 높이 있는 것을 선택할 줄 알았지만 그렇지 않았다. 결국 같은 시간 거리에 있는 물고기들을 모아서 비교해야 했다.
2. 시간이 더 오래 걸린 물고기도 후보에 넣어버렸다 즉, 가장 가까운 거리에 있는 물고기들만 fishes 리스트에 넣어야 했다.

import sys
from collections import deque

input = sys.stdin.readline

dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]
n = int(input().strip())
grid = []
sharksize = 2
cnt = 0
time = 0

for y in range(n):
    grid.append(list(map(int, input().split())))
    for x in range(n):
        if grid[y][x] == 9:
            sy, sx = y, x
            grid[y][x] = 0

canEat = True
while canEat:
    if cnt == sharksize:
        cnt = 0
        sharksize += 1
    visit = [[False for _ in range(n)] for __ in range(n)]
    visit[sy][sx] = True
    q = deque()
    q.append([sy, sx, 0])
    canEat = False
    fy, fx = 1e9, 1e9
    stopTime = 1e9
    while q:
        y, x, t = q.popleft()
        if stopTime < t:
            break
        for d in range(4):
            tmpY = y + dy[d]
            tmpX = x + dx[d]
            if n > tmpY >= 0 and n > tmpX >= 0 and \
                  not visit[tmpY][tmpX] and sharksize >= grid[tmpY][tmpX]:
                if grid[tmpY][tmpX] == 0 or grid[tmpY][tmpX] == sharksize:
                    visit[tmpY][tmpX] = True
                    q.append([tmpY, tmpX, t + 1])
                else:
                    if stopTime >= t + 1:
                        stopTime = t + 1
                        if fy > tmpY or fy == tmpY and fx > tmpX:
                            fy, fx = tmpY, tmpX
    if fy != 1e9:
        time += stopTime
        cnt += 1
        canEat = True
        grid[fy][fx] = 0
        sy, sx = fy, fx
print(time)