[SW역량테스트준비] 아기상어

아기상어

아기상어가 물고기를 먹으면서 움직이는 최단거리를 구하는 문제이다.

여러가지 조건이 까다로운 문제이다.

1. 아기상어는 자신보다 크거나, 같은 크기를 가진 물고기를 먹을 수 없다.

2. 아기상어는 상어에게 가장 가까이 있는 물고기를 우선순위로 먹어야 한다.

   1. 여러마리의 물고기가 같은 거리에 존재하는 경우가 있다.

   2. 이 경우 동일한 거리중 가장 위쪽에 있는 물고기를 우선으로 먹는다.

   3. 동일한 높이에 있을 경우, 왼쪽을 우선으로 먹는다.

3. 이 세가지 조건을 만족하면서 bfs탐색을 하기 위해서는, 최소 힙(min-heap)이 구현된 우선순위 큐를 사용하면 된다.

• 상어의 크기를 나타내는 변수를 설정한다. Ex) shark_size

• 물고기를 먹은 횟수를 나타내는 변수를 설정한다. Ex) shark_eat

• bfs에서 사용할 큐를, 우선순위 큐로 대체한다.(파이썬은 heapq를 사용하면 된다.) ex) heapq = q

• Min-heap의 우선순위는 이동 거리(d), 행 좌표(x), 열 좌표(y) 순위로 둔다.

  • 거리, 행이 가장 위쪽인 거, 열이 가장 왼쪽인 것 순서대로 우선순위가 주어지기 때문이다.

• 물고기의 크기가 상어보다 크거나 상어랑 같다면, 못먹으니까 그냥 무시하고 지나간다.

• 상어가 물고기를 먹기 전까지, 움직일 때마다 거리를 1 증가시킨다.

• 움직인 칸에 상어보다 작은 물고기가 있다면

  • 먹은 칸을 0으로 바꾼다.

  • 정답에 현재까지 이동한 거리를 더한다.

  • 먹은 횟수를 1 증가시킨다.

• 먹은 횟수가 상어의 크기와 일치한다면

  • 상어의 크기를 1 늘린다.

  • 먹은 횟수를 0으로 만든다.

• 다음 물고기를 먹기 위해 이동할 때, 이미 갔던 곳을 다시 방문할 수 있다.

  • 방문했던 곳 배열을 초기화시켜주는 작업 필요

  • 큐에 들어갔던 좌표도 전부 비워준다.

• 더이상 먹을 수 있는 물고기가 없다면 종료시켜준다.

---

code

from sys import stdin
from heapq import heappush,heappop
input = stdin.readline

n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
q = []

# 2차원 배열에 대한 입력은 끝났으니 상어가 어딨는지 찾아서 넣어주기만 하면 된다.
def init():
    for i in range(n):
        for j in range(n):
            if a[i][j]==9:
                heappush(q,(0,i,j))
                a[i][j]=0
                return

def bfs():
    size,eat,ans = 2,0,0
    check = [[False]*n for _ in range(n)]
    while q:
        d,x,y = heappop(q)

        # 먹이를 발견했다!
        if 0 < a[x][y] < size:
            eat += 1
            a[x][y] = 0
            if eat == size:
                size += 1
                eat = 0
            ans += d
            d = 0
            q.clear()
            check = [[False]*n for _ in range(n)]


        for dx, dy in (-1,0),(0,-1),(1,0),(0,1):
            nd, nx, ny = d+1, x+dx, y+dy
            # 다음 나갈 방향이 어장 밖이다!
            if nx<0 or nx>=n or ny<0 or ny>=n:
                continue
            # 다음 위치는 이미 방문 했거나, 사이즈 큰 물고기가 있다!
            if a[nx][ny] > size or check[nx][ny]:
                continue
            check[nx][ny]= True
            heappush(q,(nd,nx,ny))
    print(ans)

init()
bfs()