[백준] 16236번: 아기 상어

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

알고리즘 분류

• 구현
• 시뮬레이션
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

아기 상어가 물고기를 먹기 위해서는 고려해야 할 우선순위들이 있다.
1. 최단 거리의 물고기를 먹는다.
2. 최단 거리의 물고기가 여러 마리라면, 가장 위쪽에 있는 물고기를 먹는다.
3. 이러한 물고기도 여러 마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

입력받은 이차원 리스트 하나만 사용해서는 이걸 모두 고려한 코드를 작성하기 어려웠다. 따라서 거리를 계산하기 위한 이차원 리스트가 추가로 하나 더 필요했다.

무엇보다 이 풀이의 핵심은 우선순위 기준에 따라 정렬을 해주는 것이라고 생각한다.
bfs 탐색 시, 물고기를 먹을 수 있다고 판단되면 [거리, x좌표, y좌표] 정보를 리스트에 저장한다. 그리고 우선순위가 높은 순서대로 정렬하여 가장 우선순위가 높은 물고기를 선별한 후, 최종적으로 '먹었다' 라고 처리해주면 되는 것이다.

이 과정을 먹을 수 있는 물고기가 더 이상 없을 때 까지 반복한다.

코드

import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
direct = [(-1, 0), (0, -1), (1, 0), (0, 1)]
queue = deque([])

def bfs(start_x, start_y, size):
    distance = [[0]*N for _ in range(N)]
    visited = [[0]*N for _ in range(N)]
    priority = []

    queue.append([start_x, start_y])
    while queue:
        i, j = queue.popleft()
        visited[i][j] = 1

        for x, y in direct:
            nx = i + x
            ny = j + y

            if N > nx >= 0 and N > ny >= 0 and visited[nx][ny] == 0:
                if size >= board[nx][ny]:
                    queue.append([nx, ny])
                    visited[nx][ny] = 1
                    distance[nx][ny] = distance[i][j] + 1
                if size > board[nx][ny] > 0:
                    priority.append([distance[nx][ny], nx, ny])
    return sorted(priority, key=lambda x:(-x[0], -x[1], -x[2]))

ans = cnt = 0
size = 2
for i in range(N):
    for j in range(N):
        if board[i][j] == 9:
            board[i][j] = 2
            x = i
            y = j

while True:
    shark = bfs(x, y, size)
    board[x][y] = 0
    if len(shark) == 0:
        break

    time, x, y = shark.pop()
    ans += time
    board[x][y] = 0
    cnt += 1

    #아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다
    if cnt == size:
        size += 1
        cnt = 0

print(ans)

https://resilient-923.tistory.com/357 를 참고하였습니다.