[Python] 백준 16236 : 아기 상어

www.acmicpc.net/problem/16236

16236번: 아기 상어

풀이 방법

• 물고기를 먹으러갈 때마다 bfs로 이동한다.
• bfs로 이동하고 이동한 칸 수 만큼 answer에 더해준다. 
• 현재 상어의 크기 만큼 물고기를 먹었으면 상어의 크기 + 1해준다. 
• 틀렸던 부분 ) "먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기 -> 가장 위에 -> 가장 왼쪽에"  : 이 부분 구현은 bfs와 move의 순서 조정으로 할 수 있을 줄 알았는데, 먹을 수 있는 물고기를 다 고려해준 후에 sort를 해줘야지 정확한 답이 나온다.

전체 코드

from collections import deque
n = int(input())
arr = []
for _ in range(n):
    arr.append(list(map(int, input().split())))

sharkX, sharkY = 0, 0
for i in range(n):
    for j in range(n):
        if arr[i][j] == 9:
            sharkX, sharkY = i, j
            arr[i][j] = 0

def bfs(startX, startY, shark):
    move = [(-1, 0),(0, -1), (0, 1),  (1, 0)]
    queue = deque()
    queue.append((startX, startY, 0))
    dist = [[0] * n for _ in range(n)]
    eat = []
    while queue:
        # print(queue)
        x, y, c = queue.popleft()
        if dist[x][y] != 0:
            continue
        dist[x][y] = c
        if arr[x][y] < shark and arr[x][y] != 0:
            eat.append((c, x, y))
        for i, j in move:
            cx = x+i
            cy = y+j
            if 0 <= cx < n and 0 <= cy < n and arr[cx][cy] <= shark:
                queue.append((cx,cy, c+1))
    if not eat:
        return (-1, -1, -1)
    eat.sort()
    arr[eat[0][1]][eat[0][2]] = 0
    return eat[0]

shark = 2
answer = 0
isContinue = True
while isContinue:
    for i in range(shark):
        c, x, y = bfs(sharkX, sharkY, shark)
        # print(c)
        if c == -1:
            isContinue = False
            break
        sharkX, sharkY = x, y
        answer += c
    else:
        shark += 1

print(answer)