[백준][Python]16236번(아기 상어)

백준 16236번

✔️ 문제 풀이

◾ 준비

• 물고기의 크기 별 개수를 저장하는 fishes 배열 생성
• 아기 상어의 좌표를 shark에 저장한 후, 원래 있던 곳은 방문 및 조건 체크를 하기 수월하도록 값을 0으로 바꿔준다
• 방문체크할 visited 배열과 먹은 물고기인지를 체크할 eaten 배열을 생성한다

◾ 풀이 과정

• 접근하려는 곳이 인덱스 범위 내에 있는지 검사
• 방문가능한 곳(이전에 방문한적 없음 & 물고기가 없거나, 내 사이즈 이하의 물고기가 있음)은 무조건 큐에 넣는다

<팝하려는 원소가 먹을 수 있는 물고기일때만 아래의 과정을 실행>
-문제에서 접근해야 하는 우선순위를 설정했으므로 이에 따른 1순위의 원소를 팝해야 한다.

• 팝된 좌표가 나보다 작은 물고기이며, 먹지 않았다면(먹을 수 있는 물고기라면) 큐를 정렬한다
  ◽ 큐에서는 무조건 앞에 있는 원소가 뒤에 있는 원소보다 접근 시간이 짧다(가장 앞에 있는 원소보다 접근 시간이 더 짧은 원소는 이미 팝됐다)
  ◽ 즉, 가장 빨리 큐에 등장하는 먹을 수 있는 물고기와 동일한 시간 내에 접근할 수 있는 모든 먹을 수 있는 물고기는 이미 큐 안에 다 들어와있다.
  ◽ 정렬 기준을 times, eaten 여부, x좌표, y좌표 순서대로 설정하고, bowl[y좌표][x좌표] 값이 0이거나 동일한 사이즈인 경우를 제외하고, 가장 앞에 있는 원소를 팝한다.
• result 값을 팝한 원소의 times로 업데이트 해준다.
• 방금 먹은 물고기의 eaten 좌표를 1로 업데이트해준다.
• 방금 먹은 사이즈의 물고기의 개수를 1개 줄여준다.
• 방문체크를 해준다.
• 현재 사이즈가 된 이후로 먹은 물고기의 개수가 현재의 사이즈와 같아졌을 경우, 사이즈는 1 키워서 업데이트하고, 먹은 물고기 수는 0으로 업데이트해준다.
• 아닌 경우에는 먹은 물고기 수만 1을 더해서 업데이트해준다.
• 현재 위치에서 다시 처음부터 탐색을 시작해줘야함으로 큐를 비워준다.

◾ 결과 출력

• 내가 먹을 수 있는 물고기의 수(sum(fishes[:size]))가 0이면 bfs를 종료한다.
• 물고기가 있어도 접근불가능한 경우 큐가 비면서 자동으로 bfs가 종료된다.
• result 값을 출력한다.

최종 제출 코드

import sys
from collections import deque

input = sys.stdin.readline

n = int(input().rstrip())
visited = [[0]*n for _ in range(n)]
eaten = [[0]*n for _ in range(n)]
bowl = []
fishes = [0]*7
shark = []
dx = [0, -1, 1, 0]
dy = [-1, 0, 0, 1]

for i in range(n):
  row = list(map(int, input().split()))
  for j in range(n):
    if 1 <= row[j] <= 6:
      fishes[row[j]] += 1
    elif not shark and row[j] == 9:
      shark = (j,i,2,0,0)
      row[j] = 0
  bowl.append(row)



q = deque()
q.append(shark)
result = 0

while q:

  x, y, size, cnt, times= q.popleft()

  #############################################################################
  #                pop한 원소가 먹을 수 있는 물고기 일때만 다음 과정 실행            #
  if 0 < bowl[y][x] < size and not eaten[y][x]:
    
    q.appendleft((x, y, size, cnt, times))
    q = deque(sorted(q, key=lambda x: [x[4], eaten[x[1]][x[0]], x[1], x[0]]))
    for element in q:
      if 0 < bowl[element[1]][element[0]] < size:
        x, y, size, cnt, times= element
        break
        
    result = times
    eaten[y][x] = 1
    fishes[bowl[y][x]] -= 1
    visited = [[0]*n for _ in range(n)]

    if cnt+1 == size:
      size += 1
      cnt = 0
    else:
      cnt += 1

    
    q.clear()
  ############################################################################
  
  if sum(fishes[:size]) == 0:
    break
  
  for i in range(4):
    nx = dx[i]+x
    ny = dy[i]+y

    if nx < 0 or ny < 0 or nx >= n or ny >= n:
      continue
    # 먹진 말고 탐색만 하기
    if not visited[ny][nx] and 0 <= bowl[ny][nx] <= size:
      visited[ny][nx] = 1
      q.append((nx, ny, size, cnt, times+1))




print(result)

✔️ 실행 결과