[백준] 16236 아기 상어

문제 설명

• 조건이 많은 구현문제
• bfs를 통해 해결 가능
• 문제의 주요 내용
  • 아기 상어의 이동 조건 : 상하좌우 중 한쪽으로 이동 가능 하며 해당 칸이 비어 있거나 아기 상어보다 크기가 작거나 같을 경우
  • 아기 상어가 물고기를 먹을 수 있는 조건 : 아기 상어보다 크기가 작을 경우
    • 먹을 수 있는 물고기가 많을 때 우선순위는, 1. 거리 작은 순, 2. 가장 위(r 값 최소) , 3. 가장 왼쪽(c 값 최소)
  • 아기 상어 성장 조건 : 크기와 같은 마리수의 물고기를 먹으면 아기상어 크기 + 1
  • 탐색이 끝나는 조건(엄마 부를 때) : 더 이상 먹을 수 있는 물고기가 없을 때(물고기를 다먹었거나 나보다 큰 물고기들이 남아있다거나)
• 현재 상어의 위치에서 먹을 수 있는 물고기의 최단 거리를 찾을 때 따라서 상어의 위치가 바뀔때마다 bfs를 수행함, 이 bfs의 리턴 값은 먹을 수 있는 물고기들의 좌표와 거리의 정보가 있고 이 리스트를 거리가 길고,가장 아래쪽 좌표, 가장 오른쪽 좌표 순으로 정렬함 -> 우리가 원하는 값은 리스트이 마지막에 위치 pop사용하기 위함

코드

import sys
from collections import deque

n = int(input())
graph = []
for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))

dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]
r, c, size = 0, 0, 2

for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            r = i
            c = j
            break


def bfs(r, c, shark_size):
    distance = [[float("inf")] * n for _ in range(n)]
    q = deque([(r, c)])
    distance[r][c] = 0
    temp = []
    
    while len(q):
        cur = q.popleft()
        for i in range(4):
            nr = cur[0] + dr[i]
            nc = cur[1] + dc[i]
            if 0 <= nr < n and 0 <= nc < n and distance[nr][nc] > distance[cur[0]][cur[1]] + 1:
                if graph[nr][nc] <= shark_size:
                    q.append((nr, nc))
                    distance[nr][nc] = distance[cur[0]][cur[1]] + 1
                    if graph[nr][nc] < shark_size and graph[nr][nc] != 0:
                        temp.append((nr, nc, distance[nr][nc]))

    return sorted(temp, key=lambda x: (-x[2], -x[0], -x[1]))


fish = 0
answer = 0
while True:
    eat_fish = bfs(r, c, size)

    if len(eat_fish) == 0:
        break

    nr, nc, dist = eat_fish.pop()
    fish += 1
    answer += dist

    graph[r][c], graph[nr][nc] = 0, 0
    r, c = nr, nc

    if fish == size:
        size += 1
        fish = 0

print(answer)