BOJ 16236 - 아기 상어

풀이

---

처음으로 연습해본 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)

References

---

• BOJ 16236 - 아기 상어