[백준/Python] 16236번 - 아기 상어

<입력>         <출력>
3             3
0 0 1
0 0 0
0 9 0

<입력>         <출력>
6             60
5 4 3 2 3 4
4 3 2 3 4 5
3 2 9 5 6 6
2 1 2 3 4 5
3 2 1 6 5 4
6 6 6 6 6 6

풀이

접근법: 최단 경로를 구하는 BFS + 시뮬레이션(구현)

1. BFS + 구현

• 입력 부분: 공간에 대한 정보를 입력받으면서 아기 상어가 존재하는 행,열을 저장하고, 처음에 아기상어가 존재하는 공간의 값을 0으로 초기화
• 현재 아기 상어가 존재하는 행과 열에 대해서 BFS를 돌면서 현재 자신보다 크기가 작은 물고기가 있는지 탐색하고, 존재한다면 가장 가까운 애들부터 먹는다. (이때, 이동 거리를 result에 더해줌) 먹으러 갔을 때 위치를 현재위치로 변경
• 먹었을 때 해당 공간의 물고기는 없애주고, eat 을 증가시켜준다. (eat은 아기 상어가 먹은 물고기) 만약 아기상어가 먹은 물고기의 수(eat)과 아기상어의 현재 크기가 같다면 아기 상어의 크기를 1 증가시켜고 eat은 0으로 초기화
• 계속 크기가 자신보다 작은 물고기를 먹으러 다니면서, 만약 현재 크기가 자신보다 작은 물고기를 더이상 먹을 수 없다면 break로 while문을 빠져와서 result을 출력한다.

2. BFS

• fish 리스트로 현재 아기 상어가 먹을 수 있는 물고기의 행,열 정보와 그 물고기까지의 이동 거리를 저장
• 현재 위치에서 4방향(상,하,좌,우)으로 탐색해서 범위를 넘지 않고 만약 방문되지 않은 곳에 물고기가 존재하는데 물고기의 크기가 아기 상어의 크기보다 작다면 fish 리스트에 append 해주며, 물고기 탐색 queue에 nx, ny를 append 해준다.
• 그리고 탐색하는 공간이 빈칸(0) 이거나, 현재 아기 상어의 크기와 동일한 물고기가 존재한다면 아기상어가 지나갈 수 있기 때문에 탐색 queue에 nx, ny를 append 해준다.
• 만약 먹을 수 있는 물고기가 존재(fish 리스트의 길이가 1이상) 이라면, sort를 통해 (최단 거리의 물고기 - 행이 가장 작은 위치 - 열이 가장 작은 위치) 현재 위치에서 가장 먹을 수 있는 최단 거리의 물고기 정보를 return 해준다.

import sys
from collections import deque

### 입력 받기
n = int(input())
graph = []
for _ in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))

# 상하좌우
dx = [1,-1,0,0]
dy = [0,0,1,-1]
x,y,shark_size = 0,0,2

# 아기 상어가 먹은 물고기
eat = 0

# 아기 상어 위치
for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            x = i
            y = j
# 아기 상어가 있는 위치의 값 = 0          
graph[x][y] = 0

# 아기 상어보다 작은 물고기가 있는지 확인하면 존재한다면 가장 가까운 애들부터 먹는다.
def bfs(x,y,shark_size):
    visited = [[0] * n for _ in range(n)]
    q = deque()
    q.append((x,y,0))
    visited[x][y] = 1
    # 그 물고기까지의 이동 거리, 물고기 행과 열
    fish = []
    while q:
        x,y,dist = q.popleft()
        # 상하좌우 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 좌표 값이 유효하고, 방문한 적이 없다면
            if 0<= nx < n and 0<= ny < n and visited[nx][ny] == 0:
                visited[nx][ny] = 1
                # 물고기가 아기 상어보다 작다면
                if graph[nx][ny] != 0 and graph[nx][ny] < shark_size:
                  fish.append((dist+1,nx,ny))
                  q.append((nx,ny, dist+1))
                  visited[nx][ny] = 1
                elif graph[nx][ny] == 0 or graph[nx][ny] == shark_size:
                  visited[nx][ny] = 1
                  q.append((nx,ny,dist+1))
    
    fish.sort()        
    if fish:
      # 행이 가장 작은 위치 - 열이 가장 작은 위치 - 최단 거리의 물고기 
      return [fish[0][1],fish[0][2],fish[0][0]]
    else:
      return []

# 이동 거리
result = 0
while 1:
    bite_fish = bfs(x,y,shark_size)
    if bite_fish:
        a, b, move = bite_fish
        graph[x][y] = 0
        eat += 1
        result += move
        # 아기 상어가 먹은 물고기의 수 = 아기상어의 현재 크기
        if eat == shark_size:
            shark_size += 1
            eat = 0
        x,y = a, b
    # 더 이상 먹을 물고기가 없다면
    else:
        break
 

print(result)