[BOJ] 16236 - 아기 상어 (Python)

 

 

아이디어

 

아기 상어의 위치를 갱신하며 먹을 수 있는 가장 가까운 물고기까지의 이동 시간을 더해 나간다.

 

 

풀이

 

import sys

input = sys.stdin.readline

delta = [(-1, 0), (0, -1), (0, 1), (1, 0)]

def find_shark():
    for r in range(N):
        for c in range(N):
            if space[r][c] == 9:
                space[r][c] = 0
                return r, c

def get_fish(r, c):
    global res
    visited = [[0]*N for _ in range(N)]
    visited[r][c] = 1
    queue = [(r, c)]
    temp = []
    while queue:
        r, c = queue.pop(0)
        for dr, dc in delta:
            nr, nc = r+dr, c+dc
            if N > nr >= 0 and N > nc >= 0:
                if visited[nr][nc] == 0:
                    if space[nr][nc] in [0, size]:
                        visited[nr][nc] = visited[r][c]+1
                        queue.append((nr, nc))
                    elif space[nr][nc] < size:
                        visited[nr][nc] = visited[r][c]+1
                        temp.append((visited[r][c], nr, nc))
    if temp:
        temp.sort()
        d, r, c = temp[0]
        res += d
        space[r][c] = 0
        return r, c

N = int(input())
space = [list(map(int, input().split())) for _ in range(N)]
pos = find_shark()
res = 0
size = 2
cnt = 0
while pos:
    pos = get_fish(*pos)
    if pos:
        cnt += 1
        if cnt >= size:
            cnt = 0
            size += 1
print(res)