[BOJ 16236] 아기 상어(Python)

문제

아기 상어

---

문제 해설

조건이 많이 달려있고, 구현력이 요구되는 문제입니다. 크게 보자면 요구사항은 두가지 입니다.

1. 먹을 수 있는 물고기를 탐색합니다.
2. 상어가 이동합니다.

하지만 상어의 스펙과 제한 사항은 다음과 같습니다.

• 초기 크기는 2입니다.
• 크기가 작은 고기만 먹습니다.
• 자신의 크기만큼 고기를 먹으면 크기가 1 증가하고 먹은 횟수가 초기화됩니다.

---

그리고 상어가 이동 및 탐색을 할 때 다음과 같은 제한 사항이있습니다.

• 자신보다 큰 물고기는 통과할 수 없습니다.
• 맵 밖을 나갈 수 없습니다.
• 탐색 시 먹을 수 있는 물고기 중 가장 가까운 것을 이동 후 먹습니다.
• 가장 가까운 것이 많다면 가장 위에 있는 것을 먹습니다.
• 가장 위에 있는 것이 많다면 가장 옆에 있는것을 먹습니다.

---

제한사항이 정말 많은데, 어떤 것을 구현하고자 할 때 미리 자료구조나 정렬을 어떤식으로 써야겠다 생각하면 더 좋습니다.

저는 탐색을 할때 BFS를 써야겠다고 생각했는데 이유는 가장 가까운 물고기를 먹기 위해서입니다.

• 큰 물고기는 지나지 않습니다.

그렇게 탐색 후 먹을 수 있는 물고기인데 거리가 같을 수 있으니 리스트에 따로 모아 둡니다.

람다식을 활용해 1순위 x좌표, 2순위 y좌표를 우선순위에 두고 정렬합니다.

• 가장 가까운 것이 많다면 가장 위에 있는 것을 먹습니다.
• 가장 위에 있는 것이 많다면 가장 옆에 있는것을 먹습니다.

제한 사항을 지키기 위해서입니다. 그리고 이동합니다. 만약 먹을수 있는 물고기가 없으면 종료.

---

풀이 코드

from collections import deque

n = int(input())
graph = []
x, y = 0, 0
answer = 0
size = 2  # 상어크기
eat = 0  # 먹은 수
for _ in range(n):
    graph.append(list(map(int, input().split())))

for i in range(n):
    for j in range(n):
        # 상어 찾기
        if graph[i][j] == 9:
            x, y = i, j


def find():
    global x, y, size, eat, n
    distance = 0
    can_eat = []
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    visited = [[False] * n for _ in range(n)]
    q = deque()
    q.append((x, y))
    visited[x][y] = True

    while q:
        s = len(q)
        for j in range(s):
            a, b = q.popleft()
            for i in range(4):
                nx = a + dx[i]
                ny = b + dy[i]
                # 탐색시 자신보다 크면 안되고 맵을 벗어나면안됨
                if (
                    0 <= nx < n
                    and 0 <= ny < n
                    and graph[nx][ny] <= size
                    and not visited[nx][ny]
                ):
                    q.append((nx, ny))
                    visited[nx][ny] = True
                    # 고기를 먹을 수 있으면
                    if 0 < graph[nx][ny] < size:
                        can_eat.append((nx, ny))

        distance += 1
        # 먹을 수 있는 고기가 있으면
        if can_eat:
            # 람다식을 이용해 1순위 가장 위에있는, 2순위 가장 왼쪽에 있는 순서로 정렬
            can_eat = sorted(can_eat, key=lambda x: (x[0], x[1]))
            # 상어 위치 옮김
            graph[x][y] = 0
            graph[can_eat[0][0]][can_eat[0][1]] = 0
            x, y = can_eat[0][0], can_eat[0][1]
            eat += 1
            if eat == size:
                size += 1
                eat = 0
            break
    # 탐색이 끝났는데 먹을수 있는 물고기가 없으면
    if not can_eat:
        return 0
    return distance


while True:
    fish = find()
    answer += fish
    if fish == 0:
        print(answer)
        break