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

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

---

6개월 전에 풀었던 문젠데 한 번 더 풀었다.. 문제만 익숙했고 푸는 방식은 여전히 헷갈렸다.

 

헷갈렸던 점

• 먹을 수 있는 물고기가 한 마리보다 많으면, 거리가 가장 가까운 물고기를 먹는다.
• 거리가 가까운 물고기 많다면, 가장 위에 있는 물고기, 그러한 물고기도 많다면, 가장 왼쪽에 있는 물고기를 먹는다.

사실상 이 조건 때문에 골드 3인 거 같다. 나머지는 보통의 그래프 탐색 문제와 똑같다.

 

 

문제 풀이

문제에서 주어지는 기본 조건이 많기 때문에 미리 선언해야 한다. 상어의 크기, 상어가 먹은 물고기 개수, 상어의 위치, 총 소요 시간 등 미리 변수로 선언해 줬다.

 

그리고 처음 상어의 위치를 찾아줬다. 왜냐면 상어의 위치를 기점으로 물고기를 찾아야 하기 때문이다.

 

그 후에는 먹을 수 있는 물고기가 없을 때까지 반복문을 돌렸다. 이때 fish_list[0]은 3차원 리스트이기 때문에 상어의 x, y 좌표와 시간을 반환한다.

만약 상어 사이즈가 먹은 물고기 개수와 같아지면 상어의 크기를 +1 해주고, 먹은 개수는 다시 0으로 초기화해줘야 한다. 초기화를 안 해줬다가 틀렸다. 만약 사이즈가 2인데 두 마리를 먹었으면 3이 되고 먹은 개수는 0이 된다. 다시 세 마리를 먹어야 크기를 업그레이드할 수 있는 거다.

그리고 먹은 물고기의 위치는 0으로 바꿔준다. 이제 물고기가 없기 때문이다. 해당 물고기를 찾으러 간 시간도 반드시 총 소요시간에 더해준다.

 

find_fish 메서드는 다음과 같다.

단순한 bfs 로직이지만, 거리가 가까운 물고기부터 먹어야 하기 때문에 distance를 만들어 측정했다. 그 후 문제에서 요구하는 물고기 우선순위인 가장 가깝, 가장 위, 가장 왼쪽 순으로 정렬하였다.

이렇게 정렬하면 깔끔하게 물고기 우선순위를 뽑아서 반환할 수 있다.

 

Q. 정렬하면 시간초과 나지 않나요?

A. N이 20 이하입니다.

 

---

 

정답 코드

import sys
from collections import deque
input = sys.stdin.readline

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

def find_fish(shark_x, shark_y):
    global shark_size

    visited = [[False] * n for _ in range(n)]
    distance = [[0] * n for _ in range(n)]
    fish_can_eat = []

    dq = deque([(shark_x, shark_y)])

    while dq:
        x, y = dq.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                if graph[nx][ny] <= shark_size:
                    visited[nx][ny] = True
                    distance[nx][ny] = distance[x][y] + 1
                    dq.append([nx, ny])

                    if graph[nx][ny] != 0 and graph[nx][ny] < shark_size:
                        fish_can_eat.append([nx, ny, distance[nx][ny]])

    fish_can_eat.sort(key = lambda x : (x[2], x[0], x[1]))
    return fish_can_eat


n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
shark_x, shark_y = 0, 0
shark_size, shark_eat = 2, 0
total_time = 0
fish_list = []

for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            shark_x, shark_y = i, j
            graph[i][j] = 0

while True:
    fish_list = find_fish(shark_x, shark_y)
    
    if len(fish_list) == 0:
        break

    shark_x, shark_y, time = fish_list[0]
    shark_eat += 1

    if shark_size == shark_eat:
        shark_eat = 0
        shark_size += 1

    graph[shark_x][shark_y] = 0
    total_time += time

print(total_time)