[알고리즘][백준][python] 아기 상어

문제

 

풀이

조건

1. 아기 상어의 처음 크기 : 2
2. 먹이를 찾아 이동하는데 우선 방향은 상 -> 좌 
3. 아기 상어는 자기 크기 보다 작은 물고기만 먹을수 있음
   1. 하지만 같은 크기의 물고기 위치로는 이동할 수 있음
4. 자신의 크기 만큼 수의 물고기를 먹으면 아기 상어의 크기는 +1

1. 입력

import sys
from collections import deque

input = sys.stdin.readline

# 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
# 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.

n = int(input())
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))


dx = [0,0,1,-1]
dy = [1,-1,0,0]
cnt = 0
x,y,size = 0,0,2
#상어위치
for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            x = i
            y = j

• 먼저 사용할 매개변수를 지정하고, 상어의 위치를 찾아 저장한다.

 

2. 탐색 조건과 bfs

def biteFish(x,y,shark_size):
    distance = [[0] * n for _ in range(n)]
    visited = [[0] * n for _ in range(n)]
    # 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. (bfs사용)
    q = deque()
    q.append((x,y))
    visited[x][y] = 1
    temp = []
    while q:
        cur_x,cur_y = q.popleft()
        for i in range(4):
            nx = cur_x + dx[i]
            ny = cur_y + dy[i]
            if 0<= nx < n and 0<= ny < n and visited[nx][ny] == 0:
                if graph[nx][ny] <= shark_size:
                    q.append((nx,ny))
                    visited[nx][ny] = 1
                    distance[nx][ny] = distance[cur_x][cur_y] + 1
                    if graph[nx][ny] < shark_size and graph[nx][ny] != 0:
                        temp.append((nx,ny,distance[nx][ny]))

# 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
    return sorted(temp,key=lambda x: (-x[2],-x[0],-x[1]))

• if 0<= nx < n and 0<= ny < n and visited[nx][ny] == 0: 
  • 입력받은 그래프 범위를 벗어나거나 방문하지 않은 조건
• if graph[nx][ny] <= shark_size:
  • 그래프에 있는 물고기의 크기와 아기 상어의 크기를 비교해 먹을수 있는 고기있지 판단하는 조건
  • 먹을수 있다면 먹을수 있는 고기의 위치와 방문처리를 해준다. 또한 이동거리도 +1
  • if graph[nx][ny] < shark_size and graph[nx][ny] != 0:
    • 아기 상어가 먹을 수 있는 물고기라면 temp에 먹은 위치와 거리를 append한다. (크기가 같으면 이동만 가능) 
•     return sorted(temp,key=lambda x: (-x[2],-x[0],-x[1]))
  • lambda식을 이용해 거리, x좌표, y좌표 순으로 정렬함

상어

cnt = 0
result = 0
while 1:
    shark = biteFish(x,y,size)
    # 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
    if len(shark) == 0:
        break
    # 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
    # 정렬한 결과를 반영해준다.
    nx,ny,dist =shark.pop()
    
    #움직이는 칸수가 곧 시간이 된다.
    result += dist
    graph[x][y],graph[nx][ny] = 0,0
    #상어좌표를 먹은 물고기 좌표로 옮겨준다.
    x,y = nx,ny
    cnt += 1
    if cnt == size:
        size += 1
        cnt = 0
print(result)

그다음으로는 먹을 수 있는 물고기가 없을 때까지 while문을 돌려주면서, BFS 함수의 return 값을 받아온 뒤, 받아온 값들 중 거리 값을 result에 더해주면서 시간을 계산해주고, return 값들 중 먹은 물고기의 좌표가 담긴 nx, ny를 다음 BFS함수의 input값으로 넣어주기 위해 초기화시켜줍니다.while문 마지막에는 상어가 자신과 size 만큼의 물고기를 먹어야 사이즈가 증가하므로 해당 내용을 구현

 

NOTE

• 탐색 조건이 너무 까다로워서 많이 어려웠다
• 조건을 차근 차근 나누어 조건문을 만드는게 중요하다

참고 글

https://resilient-923.tistory.com/357

[백준] 16236(파이썬) - 아기 상어