아기 상어

풀이

백준 16236번 문제이다.
해당 문제는 상어가 deque를 이용하여 해당 위치에서 규칙을 지키면서 각 칸 까지의 최소거리를 구현하는 bfs 알고리즘을 이용한다. 각 칸까지의 거리를 나타내는 2차원 배열을 bfs 함수에서 반환하고 find 함수에서 그래프의 값이 1보다 크고 상어의 크기보다는 작을 때 즉 먹을 수 있는 물고기가 있는 칸을 찾아 그 칸까지의 최소거리가 가장 작을 때 최소거리, 인덱스를 반환한 뒤 무한 루프에서 먹을 물고기가 없는 경우에는 탈출, 아닌 경우에는 result 변수에 최소거리를 더해주고 해당 인덱스의 graph 값을 0으로 변환, 현재 상어의 위치도 인덱스로 초기화 해준다.

코드

from collections import deque
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]    
now_x, now_y = 0, 0
now_size = 2
for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            now_x = i
            now_y = j
            graph[i][j] = 0
def bfs():
    q = deque()
    q.append((now_x, now_y))
    dist = [[-1] * n for _ in range(n)]
    dist[now_x][now_y] = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= 0 and nx < n and ny >= 0 and ny < n and dist[nx][ny] == -1:
                if graph[nx][ny] <= now_size:
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))
    return dist

def find(dist):
    min_dist = int(1e9)
    distance = 0
    x, y = 0, 0
    for i in range(n):
        for j in range(n):
            if 1 <= graph[i][j] < now_size:
                if dist[i][j] < min_dist and dist[i][j] != -1:
                    x, y = i, j
                    min_dist = dist[i][j]
    if min_dist == int(1e9):
        return None
    return x, y, min_dist

result = 0
ate = 0

while True:
    value = find(bfs())
    if value == None:
        print(result)
        break
    else:
        result += value[2]
        now_x, now_y = value[0], value[1]
        ate += 1
        graph[now_x][now_y] = 0
        if ate >= now_size:
            now_size += 1
            ate = 0