풀이
처음으로 연습해본 BFS 문제이다. 처음 접하던 유형이다보니 다른 코드를 많이 참고했다.
주어진 환경에서 최단거리 내에 있는 물고기를 먹으면서 더 이상 먹을 물고기가 없어질 때 까지 아기 상어를 키우는 문제이다.
최단거리를 구하는 문제에서는 BFS 를 사용해야 한다는 점을 알고 있었지만 어떤 식으로 응요해야하는지 몰라 많이 해맸다.
우선 입력을 받으면서 처음 아기 상어의 위치를 저장해준다.
현재 아기 상어의 크기 및 위치를 고려해서 아기 상어가 먹을 수 있는 가장 가까운 물고기의 위치와 거리를 BFS 를 통해 반환한다.
BFS 를 돌리면서 아기 상어가 방문할 수 있는 좌표에 대하여 방문 처리 및 거리를 좌표에 따라 저장해준 뒤, 아기 상어가 먹을 수 있는 물고기가 있을 경우 edible 리스트에 좌표와 거리를 저장해준다.
이후 모든 탐색이 끝나면 edilbe 리스트를 거리, 맨위, 맨왼쪽 순으로 정렬한 뒤 가장 첫 번째 원소값들을 반환해준다.
이후 아기 상어의 위치를 변경하고 문제 조건에 따라서 먹은 물고기의 개수를 저장해준다.
만약 아기 상어가 먹은 개수가 자기 몸집과 같아질 경우 아기 상어의 몸집을 키운 뒤 반복한다.
만약 더 이상 아기 상어가 먹을 수 있는 물고기가 탐색에서 발견되지 않을 시 -1 을 반환하도록 하고 -1 이 반환되면 반복문을 종료한 뒤 이동한 총 거리를 출력해주면된다.
이 문제를 통해 각 상황마다 최단거리를 BFS 로 반환받고 더 이상 맞는 조건을 찾을 수 없을 때 까지 2차원 배열을 수정해주면서 반복을 해야한다는 점을 알게되었다.
소스코드
# 아기 상어
from collections import deque
import sys
input = sys.stdin.readline
def bfs(i, j): # i, j 좌표에서 현재 아기 상어가 먹을 수 있는 모든 물고기의 위치 및 거리 찾고 가장 가까운 물고기의 정보를 반환
visited = [[0] * n for i in range(n)]
visited[i][j] = 1
edible = []
dist = [[0] * n for i in range(n)]
q = deque()
q.append([i, j])
while q:
x, y = q.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0: # 한번도 간 적이 없으며 범위 내일 때
if s[nx][ny] <= s[i][j] or s[nx][ny] == 0: # 자기보다 작거나 0 일 경우 이동 가능
q.append([nx, ny])
visited[nx][ny] = 1 # 방문 처리
dist[nx][ny] = dist[x][y] + 1
if s[nx][ny] < s[i][j] and s[nx][ny] != 0: # 먹을 수 있는 물고기일 경우
edible.append([nx, ny, dist[nx][ny]]) # 그 물고기의 좌표 및 거리를 저장
if not edible: # 먹을 수 있는 물고기가 없을 경우
return -1, -1, -1
edible.sort(key=lambda x: (x[2], x[0], x[1])) # 거리, 맨위, 맨왼쪽 순으로 정렬
return edible[0][0], edible[0][1], edible[0][2]
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
n = int(input())
s = []
for i in range(n):
a = list(map(int, input().split()))
s.append(a)
for j in range(n):
if a[j] == 9: # 아기 상어 위치 확인
s[i][j] = 2
start = [i, j]
exp = 0
cnt = 0
while True:
i, j = start[0], start[1]
ex, ey, dist = bfs(i, j)
if ex == -1: break
s[ex][ey] = s[i][j] # 아기 상어가 bfs 를 통해 찾은 가장 가까운 먹이를 먹고 난 후의 위치
s[i][j] = 0
start = [ex, ey] # 새로운 시작 위치 설정
exp += 1 # 한 마리 먹었다는 정보를 저장
if exp == s[ex][ey]: # 자신의 크기와 같은 숫자의 물고리를 먹었을 때
s[ex][ey] += 1 # 크기가 1만큼 커짐
exp = 0 # 초기화
cnt += dist
print(cnt)