[백준 파이썬] #16236. 아기상어

풀기 전 생각해보기😮

• 이동 거리만큼 시간이 걸리는 점을 고려해서 BFS를 사용하자
• 2 <= N <= 20의 범위, 메모리는 512MB 가 주어지기 때문에, 시간이나 메모리 초과 오류를 감안하지 않고 구현에 집중해서 풀이할 수 있다

---

풀이🛫

from collections import deque

# target으로 가는 도중 큰 물고기는 돌아가야 함

# 이동가능한 범위
dcol = [-1,0,1,0]
drow = [0,1,0,-1]

def hunt_fish():
    global time, arr, baby_idx, baby_shark
    time += target[0]       # 이동 후 시간 갱신
    arr[baby_idx[0]][baby_idx[1]] = 0   # 현재 위치 초기화
    ncol, nrow = target[1]
    arr[ncol][nrow] = 9     # 이동한 위치에 상어 표시

    baby_shark[1] += 1     # 상어 몸집 +1
    if baby_shark[0] == baby_shark[1]:
        baby_shark[0] += 1
        baby_shark[1] = 0

    baby_idx = (ncol, nrow)
    return

def find_target():
    global target, repeat
    visited = [[0] * N for _ in range(N)]
    visited[baby_idx[0]][baby_idx[1]] = -1      # 아기상어의 시작 위치

    # 먹을 수 있는 물고기가 공간에 있는지 조회
    eatable = []

    # 도달 할 수 있는 곳인지 확인
    queue = deque()
    queue.append((baby_idx[0], baby_idx[1]))
    dist = 0
    while queue:
        dist += 1
        for i in range(len(queue)):
            col, row = queue.popleft()
            for v in range(4):
                ncol = col + dcol[v]
                nrow = row + drow[v]
                if 0 <= ncol < N and 0 <= nrow < N and visited[ncol][nrow] == 0:
                    if arr[ncol][nrow] <= baby_shark[0]:
                        queue.append((ncol, nrow))
                        visited[ncol][nrow] = dist  # 이동가능한 공간
                    else:
                        visited[ncol][nrow] = 0  # 이동할수 없는 공간

    for col in range(N):
        for row in range(N):
            if 0 < arr[col][row] < baby_shark[0] and visited[col][row] > 0:
                eatable.append((visited[col][row], (col, row)))

    if not eatable:  # eatable이 없을 때
        target = []
        repeat = False
        return
    else:  # eatable이 존재할 때
        eatable.sort(key=lambda x: (x[0], x[1][0], x[1][1]))
        target = eatable[0]
        return


def move():
    find_target()

    # 목표가 있을 때, 사냥
    if target:
        hunt_fish()

N = int(input())    # 공간의 크기
arr = [list(map(int, input().split())) for _ in range(N)]   # 9: 아기 상어
baby_shark = [2, 0]
time = 0
repeat = True

# 아기상어 위치 찾기
for col in range(N):
    for row in range(N):
        if arr[col][row] == 9:
            baby_idx = (col, row)

while repeat:
    move()

print(time)

 

핵심 정리🎁

• 이동을 위한 함수 move()를 작성하고, repeat가 True일 동안 move()를 반복 실행시켰다
• move 내부에는 사냥감을 찾는 find_target(), 사냥하는 hunt() 함수를 만들어 동작시켰다
• find_target()에서 visited를 이용해 이동할 수 있는 위치를 표시하였고, 이동가능한 곳의 값이 아기 상어의 크기보다 작을 때 eatable 리스트에 담아두었다
• 탐색을 마친 eatable 리스트는 lamda 정렬을 통해서 (위쪽, 왼쪽) 순으로 정렬될 수 있도록 했다
• target의 값이 존재한다면 hunt_fish 함수를 실행한다
• 아기 상어가 있던 지점을 0으로 초기화해주고, 사냥감이 있는 곳에 아기상어를 위치시킨다
• 이때 아기 상어가 먹은 물고기의 개수를 세서, 아기상어의 크기와 먹은 물고기의 개수가 같아질 때 상어의 몸집을 1 증가시켜주었다

 

링크💎

 

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

16236번: 아기 상어

 

후기 😎

어려웠던 점

• BFS로 거리를 계산할 생각을 하지 못해서 잘못된 결과값을 도출했었다. 아기상어와 target간의 가로, 세로  값을 더한 값을 기준으로 사용했었는데, 중간에 아기 상어보다 큰 물고기들이 있을 경우 돌아가야 한다는 점이 적용되지 않았기 때문에 다시 설정해야 했다