아기 상어 ( 16236번 )

16236번: 아기 상어

 

나의 풀이

from collections import deque
import sys

def _make_info(n):
    map_list, fish, shark_point = [], {}, ()
    for i in range(n):
        now_list = list(map(int, sys.stdin.readline().rstrip().split()))
        for j in range(len(now_list)):
            if (now_list[j] == 9): # 아기 상어 뚜루루뚜 ~
                shark_point = (i, j)
                now_list[j] = 0
            elif (now_list[j] in (1,2,3,4,5,6)): # 물고기들 뚜루루뚜 ~
                if now_list[j] not in fish:
                    fish[now_list[j]] = 1
                else:
                    fish[now_list[j]] += 1
        map_list.append(now_list)
        
    return map_list, fish, shark_point

def _eating_fish(map_list, shark_point, shark_size):
    ava_eat = [] # 거리, x, y
    visit = [[False] * n for _ in range(n)]
    visit[shark_point[0]][shark_point[1]] = 0
    queue = deque([(shark_point[0], shark_point[1])])

    while queue:
        now_x, now_y = queue.popleft()
        for next_x, next_y in ((now_x + 1, now_y), (now_x - 1, now_y), (now_x, now_y + 1), (now_x, now_y - 1)):
            if (0 <= next_x < n) and (0 <= next_y < n) and (map_list[next_x][next_y] <= shark_size) and (visit[next_x][next_y] is False):
                visit[next_x][next_y] = visit[now_x][now_y] + 1
                queue.append((next_x, next_y))
                if (0 < map_list[next_x][next_y] < shark_size):
                    ava_eat.append((visit[next_x][next_y], next_x, next_y))
    ava_eat = sorted(ava_eat, key = lambda x:(x[0], x[1], x[2]))
    """ 먹을게 없으면 False """
    return False if not ava_eat else ava_eat[0]


def _main(map_list, fish, shark_point):
    answer = 0
    shark_size, shark_eat = 2, 0
    fish = dict(sorted(fish.items(), key = lambda x:x[0])) # 이차형 로그 시간 복잡도

    """ 물고기 먹을수 있으면 """
    while fish and (next(iter(fish)) < shark_size):
        eat_fish = _eating_fish(map_list, shark_point, shark_size)
        if eat_fish is False:
            break
        else:
            use_time, eat_x, eat_y = eat_fish
            answer += use_time
            shark_eat += 1
            if (shark_size == shark_eat):
                shark_size, shark_eat = shark_size + 1, 0

            fish[map_list[eat_x][eat_y]] -= 1
            if (fish[map_list[eat_x][eat_y]] == 0): # 꺼억 꺼억 다먹음
                fish.pop(map_list[eat_x][eat_y])
                
            map_list[eat_x][eat_y], shark_point = 0, (eat_x, eat_y)
        
    return answer

n = int(sys.stdin.readline().rstrip())
map_list, fish, shark_point = _make_info(n)
print(_main(map_list, fish, shark_point))

 

시간 복잡도

while fish and (next(iter(fish)) < shark_size) : 잡아 먹을수 있는 물고기 만큼 반복 ( 이차형 시간 복잡도 )
    _find_eat(shark, map_list, shark_size, eat_shark) : bfs 탐색 ( 이차형 시간 복잡도 )
    sorted(eat_ava, key = lambda x:(x[0], x[1], x[2])) : 탐색한 bfs 정렬 ( 이차형 로그 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 사차형 로그 시간 복잡도 ( O(n**4 log n) )