[Baekjoon] 16236_아기 상어

Gold III

문제(출처: https://www.acmicpc.net/problem/16236)

---

<아기 상어>

문제 

 

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1 ×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

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

아기 상어의 이동은 1초 걸리고, 물고기를 먹는 데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

 

 

입력

 

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

0: 빈칸
1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

 

 

출력 

 

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

 

 

문제 풀이

   - my solution (Python)

import sys
from collections import deque

def baby_shark(arr, shark, shark_size,n):
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]

    visited=[[0]*n for i in range(n)] # 방문 여부
    depth = [[0] * n for i in range(n)] # 거리
    visited[shark[0]][shark[1]]=1
    queue=deque([shark])

    while queue:
        temp=queue.popleft()
        for i in range(4):
            x=temp[0]+dx[i]
            y=temp[1]+dy[i]
            if 0<=x<n and 0<=y<n:
                if arr[x][y]<=shark_size and visited[x][y]==0:
                    visited[x][y]=1
                    depth[x][y]=depth[temp[0]][temp[1]]+1
                    queue.append([x,y])
    return depth

def main():
    n=int(input()) # 공간의 크기

    arr=[]
    for i in range(n):
        arr.append(list(map(int,sys.stdin.readline().split())))

    shark_size=2 # 처음 크기
    for i in range(n): # 처음 위치
        for j in range(n):
            if arr[i][j]==9:
                shark=[i,j]
                arr[i][j]=0

    result=0
    eat_num=0 # 먹은 물고기 수
    while True:
        eat = [] # 작은 물고기
        for i in range(n):
            for j in range(n):
                if arr[i][j]!=0 and arr[i][j]<shark_size:
                    eat.append([i,j])
        depth=baby_shark(arr, shark, shark_size,n)

        min_val=n*n
        if len(eat)==0: # 더 이상 먹을 수 있는 것 x
            break

        flag=False
        for i in eat:
            if depth[i[0]][i[1]]!=0 and min_val>depth[i[0]][i[1]]: # 거리가 가까운 것 찾기
                flag=True
                min_val=depth[i[0]][i[1]]
                min_xy=[i[0], i[1]]
        if flag==True:
            result+=min_val
            eat_num+=1
            shark=min_xy
            arr[shark[0]][shark[1]]=0
        else:
            break
        if eat_num==shark_size: # 자신의 크기와 같은 수의 물고기 먹을때 크기 +1
            shark_size+=1
            eat_num=0
    print(result)

if __name__=="__main__":
    main()

 

 

• baby_shark ( 공간의 상태 , 아기 상어 위치, 아기 상어 크기, 공간의 크기)
  :  dx, dy = 상하좌우
  : visited = 방문 여부
  : depth = 거리
  : queue가 빌 때까지 반복 -> 젤 처음 값을 pop -> 상하좌우 이동하여 공간 범위 안이며 아기 상어의 크기보다 작거나 같고 (아기 상어와 크기가 같으면 지나갈 수 있으므로) 아직 방문하지 않았다면 -> 방문 표시, depth 저장 및 queue 추가
  : depth 반환
• Main
  : 공간의 크기 n 입력
  : 공간의 상태 arr 입력
  : shark_size =  아기 상어의 크기
  : shark = 아기 상어의 처음 위치 / 아기 상어의 처음 위치를 구한 후 arr의 아기 상어의 위치 값을 0으로 저장
  : result = 시간 / eat_num = 먹은 물고기 수 / eat = 아기 상어보다 작은 물고기의 위치
  : 종료 조건까지 반복 
  -> arr을 순환하여 아기 상어보다 작은 물고기의 위치를 eat에 저장 후 baby_shark 함수 호출을 통해 현재 아기 상어 위치부터 이동할 수 있는 곳의 거리를 구함 -> 만약 아기 상어보다 작은 물고기가 하나도 없다면 (eat의 길이가 0이라면) 종료 but 아기 상어보다 작은 물고기가 있다면 eat 리스트를 순환하여 거리가 가장 가까운 곳을 찾음 -> 만약 가장 가까운 곳이 있다면 result에 거리 (=시간) 추가 및 eat_num +1, 아기 상어 위치 업데이트, 물고기를 먹었으므로 arr에서 그 칸을 0으로 바꿔줌 but eat에 저장한 값이 있지만 그 칸으로 갈 수 없다면 먹을 수 없는 것이므로 종료 -> 물고기 먹은 수인 eat_num이 아기 상어의 크기인 shark_size와 같다면 아기 상어 크기 +1
  : result 출력

 

❓ 왜 틀렸는가?

아기 상어보다 작은 물고기가 있지만 그 위치로 가기 위한 depth가 0이라면 그 위치로 갈 수 없다는 뜻이다. 이 부분을 구현하는 것을 놓쳐 처음에 틀렸습니다가 발생하였다. 그래서 depth가 0이 아닐 때 min_val과 min_xy를 구하도록 구현하였다.

 

두 번째도 위와 비슷한 상황으로 아기 상어보다 작은 물고기가 있고 그 위치로 갈 수 있는 경우에 result, eat_num, shark위치, arr 정보를 수정하도록 새로운 변수 flag를 선언해주었다.

 

마지막으로는 거리가 가장 가까운 물고리를 구하기 위해 처음에 선언해준 min_val 값 때문에 틀린 것이었다. 이 부분에서 조금 오래 시간이 걸렸다. (0,0)부터 (n-1, n-1)까지 갈 수 있으므로 최대 갈 수 있는 거리는 n*n이므로 min_val을 n*n으로 선언해주어야 한다.

 

 

---

생각🤔

 

 

분명 며칠 전에 이 문제를 해결하다가 그만둔 것 같은데 아무리 찾아봐도 작성하던 코드가 없다..!

그래서 그냥 다시 구현했다..!

 

---