백준-16236-아기 상어

문제

아기 상어

풀이

문제조건 해석

아기 상어가 물고기를 잡아먹을 때 걸리는 총 시간 구하기

현재 상태를 변경해가면서 조건에 따라 BFS해줘야 한다.

• 먹을 수 있는 물고기 없으면 종료

  • 자신보다 작은 물고기만 먹을 수 있다.

• 가장 가까운 물고기를 먹는다

  • 거리가 같다면 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기

• 물고기를 먹을 때마다 크기가 증가한다.

알고리즘

아기 상태의 상태(현재위치, 크기)를 업데이트해가면서 BFS한다.

먹을 물고기 조건은 최단거리뿐만 아니라 가장 위, 가장 왼쪽 조건도 만족해야 한다.

• (거리, i좌표, j좌표) 순의 우선순위를 가지는 최소 우선순위 큐를 이용해야 한다.

• 일반 큐로 구현하게 되면 거리가 증가할 때마다 좌표값을 기준으로 정렬해줘야 한다.

• 3 0 1 2 3
  2 1 0 0 0
  0 0 0 0 0
  (숫자는 거리를 나타낸다)
  --> 오른쪽에 있는 3보다 왼쪽에 있는 3을 먼저 방문해야 한다
  

코드

from sys import stdin
import heapq
input = stdin.readline

n = int(input().rstrip())
ocean = []
for _ in range(n):
    ocean.append([int(x) for x in input().rstrip().split()])

for i in range(n):
    for j in range(n):
        if ocean[i][j] == 9:
            si, sj = i, j
            ocean[i][j] = 0  # 시작 위치 0으로 변경


def bfs(si, sj, size):
    """
    물고기를 찾아 먹는다.
    """
    time = 0
    queue = [(time, si, sj)]
    visited = {(si, sj)}
    while queue:
        for _ in range(len(queue)):
            time, i, j = heapq.heappop(queue)
            if 0 < ocean[i][j] < size:  # 자신보다 작으면 먹을 수 있다
                ocean[i][j] = 0
                return i, j, time  # 현재 좌표와 움직인 시간 반환

            for di, dj in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
                if not (0 <= i+di < n and 0 <= j+dj < n):
                    continue
                if ocean[i+di][j+dj] <= size \
                        and (i+di, j+dj) not in visited:  # 자기보다 크면 지날 수 없다.
                    visited.add((i+di, j+dj))
                    heapq.heappush(queue, (time+1, i+di, j+dj))
        time += 1
    return si, sj, 0  # 종료 조건, 움직이지 않은 상태


answer = 0
size = 2
eaten = 0 # 먹은 물고기 수
while True:
    si, sj, time = bfs(si, sj, size)
    if time == 0:
        break
    answer += time
    eaten += 1
    if eaten == size:
        size += 1
        eaten = 0
print(answer)

배운점

• 거리를 우선순위로 하는 최소 힙은 일반 큐를 이용한 BFS와 동일하다.
• BFS에서 특정 조건을 우선으로 탐색해야 할 때는 우선순위 큐를 고려하자.