[백준] 16236번. 아기상어

아이디어

아기상어가 1칸 상하좌우 이동이길래 맨해튼 거리(|x1−x2|+|y1−y2|)로 풀려고 하다가 2시간이 지나서 잘못되었다는 것을 깨닫고 문제에서 요구하는대로 구현했다.

<포인트>
1. 아기상어가 물고기를 먹는 조건과 이동 조건에 맞춰 물고기를 잡아먹는다.
2. 그 자리에서 다시 조건에 맞게 이동해서 다른 물고기를 잡아먹는다.
3. 자신의 크기만큼 물고기 개수를 잡아먹으면 +1 상어의 크기가 커진다.
3. 1-3 반복

(+ 방문 처리를 할 때 bool을 이용해야 메모리가 절약된다.)
(+ 우선순위 큐를 공부해보자! -> 람다식으로 정렬할 필요 없음)

시간복잡도

• 물고기 위치 찾기 : 이중 for문 = n x n = 20 * 20
• 물고기 잡아먹기 : deque O(1)
• 방문처리 : bool[][] -> 메모리 절약

코드

from collections import deque
import sys
input = sys.stdin.readline


# 잡아 먹을 수 있는 물고기 위치 찾기(현재 상어 위치, 상어크기)
def search_fish(shark_r, shark_c, shark_size):
    fish_list = set() # 먹을 수 있는 물고기(중복x)
    visited = [[0] * n for _ in range(n)]

    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    q = deque([(shark_r, shark_c, 0)])

    while q:
        r, c, d = q.popleft()

        # 상하좌우 탐색    
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]

            # 이동가능 범위이고 이동가능한 사이즈, 방문한 적이 없으면 지나간다.    
            if 0 <= nr < n and 0 <= nc < n and space[nr][nc] <= shark_size and not visited[nr][nc]:
                q.append((nr, nc, d + 1))
                visited[nr][nc] = 1
                
                # 먹을 수 있으면 리스트에 넣는다.
                if 0 < space[nr][nc] < shark_size:
                    fish_list.add((nr, nc, d + 1))

    # 탐색끝나고 가까운 순, 행, 열 순으로 정렬
    fish_list = list(fish_list)
    fish_list.sort(key=lambda x: (x[2], x[0], x[1]))
    # print(fish_list)
    if not fish_list:
        return 0

    return fish_list[0] # 이동할 위치 반환



# 입력값 받기
n = int(input())
space = [list(map(int, input().split())) for _ in range(n)]
shark_size = 2 
ate_count = 0
total_time = 0

# 크기별 물고기 위치 찾기
fish_dict = {s:[] for s in range(1, 7)}

for fish_r in range(n):
    for fish_c in range(n):

        # 아기상어 위치 찾기
        if space[fish_r][fish_c] == 9:
            shark_r, shark_c = fish_r, fish_c

        # 물고기 위치 저장
        elif 0 < space[fish_r][fish_c]:
            fish_dict[space[fish_r][fish_c]].append((fish_r, fish_c))


# 잡아먹을 수 있는 물고기 찾으러 가기
space[shark_r][shark_c] = 0
while True:
    fish = search_fish(shark_r, shark_c, shark_size)
    
    # 먹을 수 있는 물고기가 없으면 종료
    if fish == 0:
        break

    shark_r, shark_c = fish[0], fish[1] # 현재 상어 위치 갱신
    space[shark_r][shark_c] = 0 # 잡아먹었으면 0 처리
    ate_count += 1
    total_time += fish[2]

    # 자신의 크기만큼 잡아먹었으면 크기 +1
    if ate_count == shark_size:
        shark_size += 1
        ate_count = 0
print(total_time)