백준 16236

 

코드

from collections import deque

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

shark_size = 2
shark_x, shark_y = 0, 0
for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            shark_x, shark_y = i, j
            graph[i][j] = 0  # 상어 위치는 빈칸으로 처리
            break

dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]  # 북, 서, 남, 동

def bfs():
    dist = [[-1] * n for _ in range(n)]
    q = deque([(shark_x, shark_y)])
    dist[shark_x][shark_y] = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if dist[nx][ny] != -1 or graph[nx][ny] > shark_size:
                continue
            dist[nx][ny] = dist[x][y] + 1
            q.append((nx, ny))
    return dist

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

result = 0
ate = 0
while True:
    value = find(bfs())
    if value is None:
        print(result)
        break
    else:
        shark_x, shark_y = value[0], value[1]
        result += value[2]
        graph[shark_x][shark_y] = 0
        ate += 1
        if ate >= shark_size:
            shark_size += 1
            ate = 0