[ 16236 ] [ BFS ] 아기 상어

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

 

---

풀이 과정

---

1. 현재 아기 상어의 위치를 찾아 두고, 아기 상어의 위치를 조정해주는 방식으로 진행하면 된다.
2. 다음에 사냥할 물고기는 BFS를 통해서 찾아준다.
   1. 단, 이 때 현재 아기 상어의 크기보다 큰 물고기로는 이동 불가능, 크기와 같은 물고기는 이동은 가능하지만 사냥 불가능한 점에 유의해서 BFS 수행
   2. 사냥 가능한 물고기가 등장하게 되면, 이동 길이를 저장해 두고 이동 길이가 같으면서 사냥 가능한 물고기가 또 있는지 찾아본다.
   3. 사냥 가능한 물고기 리스트를 행 기준으로 1차 정렬, 열 기준으로 2차 정렬해 준다. ( 거리는 모두 같으므로 고려할 필요 없이 좌표상 맨 위에 있어야 하며, 같은 행인 경우는 맨 왼쪽에 있어야 하므로 )
   4. 정렬된 물고기 리스트의 첫번째 요소가 사냥할 물고기의 위치이다.
3. 상어의 위치를 사냥할 물고기의 위치로 이동시키고, 이동 거리를 더해준다.
4. 상어의 현재 크기에서 사냥한 물고기의 수가 현재 크기가 된다면 상어의 크기를 하나 올려주고 사냥한 물고기 수를 0으로 초기화시켜 준다.
5. 사냥이 불가능할 때까지 2-4 과정을 반복한다.
6. 누적 이동 거리를 출력시켜 준다.

---

소스 코드

---

import sys
from collections import deque


input = lambda: sys.stdin.readline().rstrip()

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

# row, col, level
babyshark = [0, 0, 2]

for i in range(n):
    for j in range(n):
        if matrix[i][j] == 9:
            babyshark[0], babyshark[1] = i, j

def get_next_fish(babyshark):
    global n
    queue = deque([[babyshark[0], babyshark[1], 0]])
    visited = set()
    visited.add((babyshark[0], babyshark[1]))
    dx = [-1, 0, 0, 1]
    dy = [0, -1, 1, 0]

    minimum = int(10e9)
    candidate = []
    while queue:
        x, y, mv = queue.popleft()
        if mv == minimum:
            break
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx and nx < n and 0 <= ny and ny < n and \
               (nx, ny) not in visited and \
               matrix[nx][ny] <= babyshark[2]:
                queue.append([nx, ny, mv+1])
                visited.add((nx, ny))
                if matrix[nx][ny] != 0 and matrix[nx][ny] != 9 and \
                   matrix[nx][ny] < babyshark[2]:
                    minimum = mv+1
                    candidate.append([nx, ny])
    if candidate:
        candidate.sort(key=lambda x:(x[0], x[1]))
        return candidate[0][0], candidate[0][1], minimum
    else:
        return -1, -1, minimum
    

    
time = 0
eat_count = 0
while True:
    x, y, dist = get_next_fish(babyshark)
    if x == -1 and y == -1:
        break
    time += dist
    matrix[babyshark[0]][babyshark[1]] = 0
    babyshark[0], babyshark[1] = x, y
    matrix[babyshark[0]][babyshark[1]] = 9
    eat_count += 1
    if eat_count == babyshark[2]:
        babyshark[2] += 1
        eat_count = 0

print(time)