[알고리즘] 백준 16236 아기 상어

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

정글에서의 알고리즘 주차는 끝났지만, 개인적으로 매일 알고리즘 한 문제씩은 풀이하려고 한다.
그 중에서도 나는 구현 문제에 유독 약하다고 생각해서 구현 문제를 한 문제 골라 풀어보았다.

단순 bfs 문제라고 생각했지만, 생각보다 까다로운 조건들이 많았고 결국 풀이를 보게 되었다.
처음 접하는 테크닉이 들어가 있는 문제라서 한번 정리해보려고 한다.

가장 이해가 안갔던 문제의 조건은 다음 문장이었다.

거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

이를 조금 개발적으로 해석해보면, 아기 상어가 위치한 좌표에서 먹을 수 있는 물고기들의 좌표들을 다음의 우선 순위로 정렬하라는 의미와 같았다.

1. 아기 상어에서 물고기까지의 거리
2. 해당 물고기의 x좌표
3. 해당 물고기의 y좌표

자세한 설명은 주석에 첨부하였다.

정답 코드

import sys
from collections import deque

N = int(sys.stdin.readline())

graph = []
x, y, size = 0, 0, 2

for i in range(N):
    row = list(map(int, sys.stdin.readline().split()))
    for j in range(N):
        if row[j] == 9:
            x, y = i, j
    graph.append(row)

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

def bfs(x, y, shark_size):
    distances = [[0 for _ in range(N)] for _ in range(N)]
    visited = [[False for _ in range(N)] for _ in range(N)]

    queue = deque()
    queue.append([x, y])
    visited[x][y] = True
    temp = [] # 상어 위치에서 먹을 수 있는 물고기들의 정보를 담을 리스트 선언

    while queue:
        px, py = queue.popleft()
        for i in range(4):
            nx = px + dx[i]
            ny = py + 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
                    queue.append([nx, ny])
                    # 물고기를 먹기까지 걸리는 거리(시간)을 이동마다 업데이트 해준다.
                    distances[nx][ny] = distances[px][py] + 1 
                    if 0 < graph[nx][ny] < shark_size:
                        temp.append([nx, ny, distances[nx][ny]])

    # 내림차순 정렬 후 뒤에서 pop() 하는 것이 오름차순 정렬후 pop(0) 하는것보다 시간복잡도에서 이득임
    return sorted(temp, key=lambda t: (-t[2], -t[0], -t[1]))

count = 0
result = 0
while True:
    # 현재 상어 위치에서 먹을 수 있는 물고기들 위치와 거리값 반환
    shark = bfs(x, y, size)

    # 더 이상 먹을 수 있는 물고기가 없으면 종료
    if not len(shark):
        break

    px, py, pdist = shark.pop() # 현재 위치에서 먹을 수 있는 물고기중에서 가장 가까운 물고기를 잡아 먹는다.

    result += pdist # 가장 가까운 물고기를 잡아먹을 수 있는 거리가 곧, 해당 물고기를 잡아먹는데 걸리는 시간이다.
    graph[x][y], graph[px][py] = 0, 0  # 이전에 상어가 있던 자리와 물고기를 먹은 자리의 값을 0으로 초기화 시킨다.

    x, y = px, py # 상어 좌표를 방금 먹은 물고기의 위치로 이동시킨다.
    count += 1 # 먹은 물고기 수 1증가

    if count == size: # 먹은 물고기 수가 현재 사이즈와 같다면, 상어 사이즈 업!
        size += 1
        count = 0

print(result)