Q46. 아기상어

16236번: 아기 상어 (acmicpc.net)

16236번: 아기 상어

 

실수할 거리가 너무 많은 문제..

문제를 잘 읽고 잘 이해하고 잘 정리한다음에 차근차근 구현하고

디버깅도 잘 해야된다.

직접 예시를 만들어 시뮬레이션 해보는것도 오래걸리기 때문에 애초에 코드 구현 자체를 꼼꼼하게 잘 해야됨.

 

from collections import deque

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(grid, cur_scale, x, y):
    INF = 1e10
    N = len(grid)
    mindist = [[INF] * N for _ in range(N)]

    q = deque()
    q.append((x, y, 0))

    while q:
        x, y, dist = q.popleft()

        if mindist[x][y] < INF:
            continue

        mindist[x][y] = dist

        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:
                if grid[nx][ny] > cur_scale:
                    continue
                
                q.append((nx, ny, dist + 1))

    return mindist

def eat_closest(grid, cur_scale, x, y):
    mindist = bfs(grid, cur_scale, x, y)

    N = len(grid)
    minx = -1
    miny = -1
    closest_dist = 1e10
    for i in range(N):
        for j in range(N):
            if grid[i][j] > 0 and grid[i][j] < cur_scale and mindist[i][j] < closest_dist and mindist[i][j] > 0:
                closest_dist = mindist[i][j]
                minx = i
                miny = j
    
    if closest_dist == 1e10:
        return -1, -1, -1

    grid[x][y] = 0

    return closest_dist, minx, miny

def start(grid):
    x, y = 0, 0
    N = len(grid)

    for i in range(N):
        for j in range(N):
            if grid[i][j] == 9:
                x, y = i, j
                grid[i][j] = 0
    
    ate = 0
    cur_scale = 2
    time = 0
    while True:
        moved, x, y = eat_closest(grid, cur_scale, x, y)

        if moved == -1:
            print(time)
            break

        time += moved
        ate += 1

        if ate == cur_scale:
            cur_scale += 1
            ate = 0

start(grid)