[BOJ] 16236 아기상어

# 16236번 아기상어
# N*N 크기에 물고기 M마리 아기상어 1마리
# 아기상어 초기 크기는 2,
# 자기보다 큰 물고기는 먹기x 지나가기 x
# 자기와 같은 물고기 먹기x, 지나가기 o
# 자기보다 작은 물고기 먹기 o 지나가기 o
# 아기상어는 자기 크기 만큼의 횟수만큼 물고기를 먹는다면 크기가 1 증가한다.
# 먹을 수 있는 물고기가 없으면 엄마상어에게 가기
# 먹을 수 있는 물고기가 1마리면 거리가 가장 가까운 물고기를 먹으러간다.
# 먹을수 있는 물고기가 가장 가까운 거리에 있는걸 먹는다. 위 1순위 왼쪽 2순위 위로 정렬 왼쪽으로 정렬 2중정렬
# 1~6 은 물고기 9은 아기상어 위치
dx = [-1,1,0,0]
dy = [0,0,-1,1]
N = int(input())
aquarium = [list(map(int,input().split())) for _ in range(N)]
fishs = []
for x in range(N):
    for y in range(N):
        if aquarium[x][y]:
            if aquarium[x][y] == 9:
                shark_x = x
                shark_y = y
time = 0
shark_size = 2
shark_eat = 0
flag = True
while flag:
    eat_fishs = []
    visited = [[0]*N for _ in range(N)]
    shark = []
    shark.append((shark_x,shark_y,0))
    visited[shark_x][shark_y] = 1
    while shark:
        x,y,distance = shark.pop(0)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < N and 0<= ny< N:
                if not visited[nx][ny]:
                    if aquarium[nx][ny] > shark_size:
                        continue
                    else:
                        visited[nx][ny] = 1
                        if aquarium[nx][ny] == shark_size or aquarium[nx][ny] == 0:
                            shark.append((nx,ny,distance+1))
                        else:
                            shark.append((nx,ny,distance+1))
                            eat_fishs.append((nx,ny,distance+1))
    if not len(eat_fishs):
        break
    else:
        eat_fishs.sort(key=lambda x: (x[2],x[0],x[1]))
        aquarium[shark_x][shark_y] = 0
        shark_x = eat_fishs[0][0]
        shark_y = eat_fishs[0][1]
        shark_eat += 1
        aquarium[shark_x][shark_y] = 9
        time += eat_fishs[0][2]
        if shark_eat == shark_size:
            shark_size += 1
            shark_eat = 0
print(time)
            
    

 

 

 

 아기상어 문제는 조건들을 정리하는 것이 먼저였다.

1. 상어보다 작거나 같은 크기의 물고기들은 지나갈수 있다.

2. 상어는 자기보다 작은 물고기만 먹는다.

3. 가장 가까운 물고기를 먼저 먹는다.

4. 같은 위치에 존재하면, x축이 작은 것을 1순위, y축이 작은것이 2순위이다.

5. 상어의 크기의 개수만큼의 물고기를 먹으면 상어가 커진다.

 

이 부분을 정리하고 풀면 쉬웠다.

 

기본적으로 BFS를 하는대신 상대적인 거리를 측정하기 위한 distance를 넣어주었다.

그래서 상어가 먹을 수 있는 모든 물고기의 위치를 파악해주고, 거리를 측정해주었다.

여기서 시간을 더 줄이고 싶으면, 어차피 BFS이기 때문에 최소거리로 측정이 된다.

그러므로, 최초로 먹을수 있는 물고기와의 거리를 측정하고 그 거리보다 큰 것들이 나오는 순간 BFS를 멈춰도 된다.

 

하지만 시간제한이 널널한 편이었고, 첫시도였기 때문에, 머리로만 생각하고 넘어갔다.

위와 같이 먹을 수 있는 물고기목록을 구한뒤에는 lambda를 통한 다중정렬을 해서 문제 조건에 맞게 오름차순으로 정리해준다.

그리고 선택된 물고기의 위치를 상어의 위치로 바꿔주고, 상어의 크기와 상어의 먹은 물고기의 수를 비교해줘서 같아지면 상어의 크기를 키워주고 먹은 물고기 수를 초기화 시켜줬다.

 

이 문제에서 시간이 좀 걸렸던 요인은 움직인 상어의 이전 위치의 좌표를 초기화 안 시켜줘서 생겼다. 그냥 상어의 최초위치만 파악하고 난뒤에는 상어의 위치는 지속적으로 추적이 가능하므로, 그냥 상어의 값을 0으로 바꿔주는게 더 편할수 있을 것 같다.