[백준/Python] 16236번 아기 상어

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

16236번: 아기 상어

---

---

Solution

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

#baby_shark(level, position, count)

def eat(pos):
    global answer, baby_shark, space
    bsp = baby_shark[1]
    q = deque()
    q.append(bsp)
    visited = [[False] * n for _ in range(n)]
    visited[bsp[1]][bsp[0]] = True
    distance = 0
    state = False
    eatable = []
    
    while q:
        distance += 1
        for _ in range(len(q)):
            x, y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or nx >= n or ny < 0 or ny >= n:
                    continue
                if space[ny][nx] <= baby_shark[0] and visited[ny][nx] == False:
                    visited[ny][nx] = True
                    if 0 < space[ny][nx] < baby_shark[0]:
                        eatable.append((nx, ny))
                        state = True
                    else:
                        q.append((nx,ny))
        if eatable:
            break

    if eatable:
        eatable = sorted(eatable, key = lambda x:(x[1],x[0]))
        space[eatable[0][1]][eatable[0][0]] = 9
        space[bsp[1]][bsp[0]] = 0
        baby_shark[1] = eatable[0]
        baby_shark[2] -= 1
        if baby_shark[2] == 0:
            baby_shark[0] += 1
            baby_shark[2] = baby_shark[0]
        answer += distance
        return True
    else:
        return False
        
        

n = int(input())
answer = 0
space = []
eatable = []

for _ in range(n):
    space.append(list(map(int, input().split(' '))))

baby_shark = [2, (0,0), 2]

for i in range(n):
    for j in range(n):
        if space[i][j] == 9:
            baby_shark[1] = (j,i)
            pos = (j, i)
            space[i][j] = 0
            break

while True:
    if not eat(pos):
        break

print(answer)

 

BFS를 사용하여 풀었다. baby_shark에는 차례대로 baby_shark의 크기, 위치, 물고기를 먹는 횟수가 들어간다. 처음에 공간에서 아기 상어의 위치를 구해 0으로 초기화 하고 eat함수에 좌표를 넘겨준다. eat함수에서는 queue에 먼저 아기 상어의 위치bsp를 넣고, while문을 돌린다. 근데 이때, while문 안에 queue의 길이만큼 for문을 돌려주면서 거리를 구한다. 즉 for문이 queue의 길이만큼 돌면, 거리가 1씩 증가한다. 그리고 for문을 돌면서 0보다 크면서 baby_shark[0]보다 작으면 먹을 수 있는 물고기 이므로 eatable에 넣어준다. 먹을 수 있는 물고기가 있으면 while문을 빠져나오고, 같은 거리에서 여러 마리가 존재할 수 있으므로 문제 조건 대로 정렬을 해준다. 그리고 space와 baby_shark를 갱신해주고 answer에 distance를 더해준다. 이 과정을 eatable이 더 이상 나오지 않을 때 까지 반복한다. 

처음에는 eatable를 구하는 로직을 함수로 분리하고, distance 배열을 하나 만들어 eatable에 거리까지 넣고, 비교하면서 정렬하고 직접 answer에 더해주는 방식으로 구현을 했다. 예제도 다 맞길래 제출했는데 짤 당했다.😄그래서 머리 싸매다가 찾아본 결과 queue의 길이만큼 돌려주면서 거리를 구하는 방식을 알게 되었고 그걸로 풀었다.