[boj 16236] [Python] 아기 상어

초안입니다

문제 이해하기

아래 반복

1. target 결정
   1. target 없으면 종료
2. 먹기
   1. 갯수 채우면 성장
   2. 아니면 그냥 넘어감

왜 안 돼?

• type을 결정하지 않고 return 하는 것은 강력하지만, return None 어떻게 취급되는지 알 필요 있다

• findPrey 함수 3번 수정함

• 마지막으로 고친 것: 단순히 가장 가까운 먹이를 bfs 하는 것만으로는 문제의 조건(먹이선택조건)을 맞출 수 없다. 나는 큐에 넣는 순서를 상-좌우-하로 맞추면 가능할 줄 알앗는데 아님 (조금 생각해보면 아ㅣ니라는걸알수잇다)

• 그래서 모든 먹이에 대해 기억해두고 정렬

  • 정렬 기준: 1순위 - 거리 , 2순위 - x좌표, 3순위 - y좌표

코드

from collections import deque
from sys import stdin

input = stdin.readline


def findPrey(board, n, size, shark):
    # 가장 가까운 먹이의 위치와 거리를 return

    # 상좌우하순서 
    dx = [0, -1, 1, 0]
    dy = [1, 0, 0, -1]

    visited = [[0 for _ in range(n)] for _ in range(n)]

    q = deque()
    q.append((shark[0], shark[1])) # 현재위치 방문
    visited[shark[0]][shark[1]] = 1

    eat = []
    while q:
        x, y = q.popleft()
        # 모든 먹이에 대해 거리 계산
        for d in range(4):
            xx, yy = x+dx[d], y+dy[d]
            if xx >= 0 and xx < n and yy >= 0 and yy < n:
                if board[xx][yy] <= size and visited[xx][yy]==0:
                    visited[xx][yy] = visited[x][y] + 1
                    q.append((xx, yy))
                if board[xx][yy] < size and board[xx][yy] > 0:
                    eat.append((xx, yy, visited[xx][yy]-1))
    
    eat.sort(key=lambda x:(x[2],x[0],x[1]))
    if eat:
        return eat[0]
    else:
        return None



n = int(input())
board = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    board[i] = list(map(int, input().split()))
# 입력 끝

for i in range(n):
    for j in range(n):
        if board[i][j] == 9:
            shark = (i, j)
            board[i][j] = 0
# 현재 상어의 위치
size = 2    # 기본 사이즈 
count = size # 먹이 먹은 수

t = 0
target = findPrey(board, n, size, shark)
    
while target:
    t += target[2] # distance 더함
    shark = (target[0], target[1])   # 이동
    board[target[0]][target[1]] = 0 # 먹힘 ㅠㅠ 
    count -= 1
    if count == 0:
        size += 1
        count = size
    target = findPrey(board, n, size, shark)
    
    

print(t)