[백준BOJ] 16236번 아기 상어.py

 

백준 저지에서 아기 상어를 파이썬을 통해 풀어 보았다. 

 

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

16236번: 아기 상어

16236번 아기 상어.py

tomy9729/Algorithm

 

16236번 아기 상어

문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.
아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.
아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.
아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

- 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
- 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
- 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
- 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야 하는 칸의 개수의 최솟값이다.
- 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러 마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈칸이 된다.
아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.
공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

설명

귀여운 제목에 비해 난이도는 그렇지 않았던 문제이다. 특히 조건이 엄청 많다. 

 

아기 상어는 자신보다 작은 물고기를 잡아먹을 수 있다. 아기 상어가 먹을 수 있는 크기의 물고기가 더 이상 없으면 엄마 상어를 부른다. 아기 상어가 엄마 상어를 부르기 전까지 물고기를 먹는 시간을 구하는 문제이다. 단 아기 상어는 자기 크기만큼 물고기를 먹으면 커지며 자기보다 큰 물고기가 있는 곳으로는 이동할 수 없다.

 

문제의 조건이 너무 많기 때문에 객체화할 필요가 있었다. 작은 문제부터 해결하기 위해 노력했다. 

 

아기 상어는 자기보다 크기가 작은 물고기만을 먹을 수 있다. 그리고 아기 상어는 물고기가 없거나, 자기보다 작거나 같은 크기의 물고기가 있는 곳으로만 이동할 수 있다. 좌표 위에서 아기 상어가 먹을 수 있는 물고기를 찾는 게 첫 번째 문제이다. 이렇게만 생각하면 단순한 BFS문제이다. 아기 상어의 위치에서 상하좌우 중 이동할 수 있는 위치로 이동한다. 그렇게 이동하다가 아기 상어가 먹을 수 있는 물고기를 만나면 해당 위치를 체크한다.

 

다음은 어떤 물고기를 먹을 것인가에 대한 결정 문제이다. 우선적으로 아기 상어가 위치에서 아기 상어가 먹을 수 있는 가장 가까운 물고기를 찾는다. 단 해당 물고기가 여러 마리일 수 있다. 결정에 있어 우선 조건은 아기 상어로부터 최소 이동 거리이기 때문에 같은 거리에 있는 아기 상어가 먹을 수 있는 물고기들의 위치와 이동거리(시간)를 별도의 배열에 모아 놓는다. 만약 배열에 있는 물고기들보다 더 멀리 있는 물고기에 접근하면 BFS를 그대로 종료하고 배열을 반환한다. 만약 처음부터 아기 상어가 먹을 수 있는 물고기가 없다면 빈 배열을 반환할 것이다. BFS의 역할은 여기까지다.

 

메인 함수에서 무한 반복문을 통해 BFS를 계속 수행한다. 만약 빈 배열이 반환되었다면 아기 상어가 먹을 수 있는 물고기가 없다는 것이며 즉 엄마 상어를 불러야 한다. 이때 무한 반복문을 멈춘다.

 

빈 배열이 아니라면 배열에는 아기 상어로부터 최소 이동 거리에 있는 "아기 상어가 먹을 수 있는 물고기"의 모음일 것이다. 아기 상어가 먹을 물고기의 우선순위에 따라 배열을 정렬해주고 아기 상어가 먹게 될 물고기를 가져온다. 다음으로 "아기 상어가 물고기를 먹는 상황"을 구현한다. 아기 상어가 물고기를 먹었으므로 해당 좌표에 물고기는 사라지고 아기 상어가 위치한다. 아기 상어가 먹은 물고기 수에 한 마리 추가된다. 아기 상어가 원래 위치에서부터 해당 물고기까지 이동한 시간이 추가된다. 만약 아기 상어가 먹은 물고기 수와 아기 상어의 크기가 같다면 아기 상어의 크기가 1만큼 커진다. 

 

무한 반복문을 통해 아기 상어의 식사를 반복하다 앞서 말한 것처럼 빈 배열이 반환되면 무한 반복문을 종료하고 현재까지 계산한 시간을 출력한다.

 

처음 문제를 읽었을 때는 여러 조건들때문에 머리가 복잡했는데 막상 문제를 풀다보니 그저 조건이 많은 단순 BFS문제일 뿐이라서 엄청 어렵지는 않은 것 같다. 그래도 상당히 재미있는 문제였다.

코드

#16236번 아기 상어
from collections import deque
def BFS(area,visit,baby_i,baby_j,baby_size,n) :
  eat_fish = []
  di = [0,0,1,-1]
  dj = [1,-1,0,0]
  visit[baby_i][baby_j] = True
  q = deque()
  q.append([baby_i,baby_j,0])
  while q :
    now = q.popleft()
    for index in range(4):
      next_i = now[0]+di[index]
      next_j = now[1]+dj[index]
      if 0<=next_i<n and 0<=next_j<n: #존재하는 배열이면
        if visit[next_i][next_j]==False and 0<= area[next_i][next_j] <= baby_size :#아직 방문하지 않은 점 and 아기 상어가 지나갈 수 있으면
          visit[next_i][next_j]=True # 방문
          q.append([next_i,next_j,now[2]+1]) #큐에 추가
          if 1<= area[next_i][next_j] < baby_size : #아기 상어가 먹을 수 있으면
            if (not eat_fish) or eat_fish[-1][2] == now[2]+1: # 최소 거리에 있는 모든 먹을 수 있는 물고기
              eat_fish.append([next_i,next_j,now[2]+1])
            else : return eat_fish # 최소 거리보다 더 멀리 있는 "먹을 수 있는 물고기"에 접근하면 종료
  return eat_fish #먹을 수 있는 물고기가 없으면 종료

if __name__ == "__main__":
  n = int(input())
  area=[]
  baby_i=0 #아기상어의 초기 위치
  baby_j=0
  baby_size=2 #아기 상어의 초기 크기
  baby_eat=0 #아기 상어가 먹은 물고기수
  for i in range(n) : 
    area.append(list(map(int,input().split())))
    for j in range(n) :
      if area[i][j]==9:
        baby_i=i
        baby_j=j
  visit = [[False]*n for _ in range(n)]
  time = 0 #시간

  while True : 
    visit = [[False]*n for _ in range(n)] #노드 방문 초기화
    fish = BFS(area,visit,baby_i,baby_j,baby_size,n)#아기 상어가 먹을 수 있는 물고기 후보군들
    area[baby_i][baby_j]=0 #아기 상어의 원래 위치 0으로 변환
    if not fish : #먹을 수 있는 물고기가 없으면 즉 엄마 상어를 불러야하면 종료
      break
    fish = sorted(fish,key=lambda x : (x[0],x[1])) #조건에 맞춰 물고기들 정렬
    fish = fish[0] #아기 상어가 먹은 물고기
    time += fish[2] #시간 추가
    area[fish[0]][fish[1]]=0 #아기 상어가 먹은 물고기의 위치 0으로 변환 (아기 상어가 먹었으므로)
    baby_i = fish[0] #아기상어의 위치 변환 (아기 상어가 먹은 물고기의 위치)
    baby_j = fish[1]
    area[baby_i][baby_j]=9 #아기 상어의 위치
    baby_eat+=1 # 아기 상어가 먹은 물고기 추가
    if baby_eat == baby_size : # 아기 상어가 자기 몸 크기만큼 물고기를 먹으면 아기 상어 크기 증가
      baby_size+=1
      baby_eat=0
  print(time)