[백준/16236/파이썬] 아기 상어

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

16236번: 아기 상어

Problem

• N×N 크기의 공간에 물고기 M마리와 아기 상어 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: 아기 상어의 위치

SOL

문제에 조건이 주렁주렁 달린 빡구현 문제이다. 하지만, 상어의 이동 1개에 조건이 자세하게 붙은 경우라서, 상어의 이동을 잘 구현해주면 된다.

상어

• 자신이 위치하는 좌표
• 크기
• 먹은 먹이갯수

상어의 움직임.

 

문제 발생 

1. 방문체크 배열을 선언 해주냐 vs 안해주냐.

• 문제가 되는건, 물고기를 먹고나서, 다른 곳에 물고기가 있는지 확인하는 과정에서 발생한다. 
• 그리고, 무한반복과 먹을 물고기가 없는 경우도 생각해줘야 하기 때문에, 방문 chk는 필수이다.
• 그러므로, 물고기를 먹었을 때, 추가적으로 처리를 해주는게 맞다.
  • 물고기를 먹었을 때, 방문 배열을 초기화 해주고, dq를 비워준다. (재시작)

2. BFS를 이용하면, 최단거리로 움직이는건 보장이 되어있기 때문에, 거리가 같은 경우가 문제가 발생하게 된다.

이 상어 친구는 거리가 가까운 물고기부터 먹는 똑똑한 상어이다. 거리가 같은 경우에 가장 위에 있는 물고기, 그 중에서도 가장 왼쪽에 있는 물고기부터 먹는다.

처음에 이 부분을 구현을 안해주고, deque로 그냥 시뮬레이션을 했다. (몇개의 예제는 무리없이 통과된다)

그렇다면, ny,nx를 기준으로 sorting이 필요한데, deque로 bfs를 구현하지말고, 우선순위 큐를 이용해서, 자료를 자동으로 관리되게끔 구현하면 훨씬 편하다. (파이썬은 min_heap이므로, 그냥 그대로 쓰면 된다. 가장 왼쪽,가장 위로 갈 수록, 좌표는 줄어들기 때문) 이건 블로그를 찾아보다가, 엄청 좋은 방법같아서, 저도 쓰게 됬습니다. 와, 한번도 deque대신 heapq를 사용할 생각은 안해봤다.

 

그렇게되면,그 외에 부분은 구현이 정말 간단하다.

# ㅇ ㅏ ㄱ ㅣ 상어 ~ 뚜루뚜뚜
import sys
from heapq import heappop,heappush
input = sys.stdin.readline
dx=[-1,0,1,0]
dy=[0,1,0,-1]
N =int(input().rstrip())
board=[list(map(int,input().split())) for _ in range(N)]
q=[]
# shark는 distance, y의 좌표,x의 좌표를 우선순위로 움직인다.
def init():
    for i in range(N):
        for j in range(N):
            if board[i][j] ==9:
                heappush(q,(0,i,j))
                board[i][j] =0
                return

def moving():
    size,eat,ans=2,0,0
    visited=[[False]*N for _ in range(N)]
    while q:
        d,y,x = heappop(q)
        if 0<board[y][x]<size:
            eat+=1
            board[y][x]=0
            if eat ==size:
                size+=1
                eat=0
            ans+=d
            #다시 왔던길로 갈 수 있으므로, 초기화
            d=0 
            while q:
                q.pop()
            visited=[[False]*N for _ in range(N)]
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            nd=d+1
            if ny<0 or ny>=N or nx<0 or nx>=N:
                continue
            if 0<board[ny][nx]>size or visited[ny][nx]:
                continue
            visited[ny][nx] = True
            heappush(q,(nd,ny,nx))
    print(ans)

init()
moving()

 

참고한 블로그 -

 

https://rebas.kr/714

BOJ 16236 · 아기 상어