[백준][Python] 16236번 아기상어 - 코팩

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

풀이

 

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. -> 입력값에 대한 설명, 공간의 크기와 공간에서 물고기와 빈칸, 아기상어의 위치

 

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. -> 상하좌우로만 움직일 수 있으며 아기상어의 크기는 2이다.

 

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. -> 본문그대로 읽으면 이해하는데 무리가 없을 것이다.

 

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. 
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다. -> 먹을 수 있는 물고기의 후보가 여러마리라면 맨 위에 있는 물고기를, 그것도 맨 왼쪽에 있는 물고기를 최우선 순위로 먹는다. 항상 최단거리에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다. -> 아기상어의 크기는 2에서 시작하며 자신의 크기만큼 물고기를 잡아먹으면 크기가 1 증가하며, 잡아먹은 물고기의 개수는 0에서부터 다시 센다.

 

종합적으로 보면 먹을 수 있는 물고기 중 최단거리에 있는 물고기를 우선순위로 먹으면서 상어가 돌아다니는 시간을 계산하는 문제인데

bfs를 이용해서 먹을 수 있는 물고기를 찾아낸 뒤, 최단거리를 가진 물고기 중 위에 있으며 왼쪽에 있는 물고기를 선택하여 아기상어를 움직이게하여 물고기를 잡아먹게한다.

코드

    # 16236번 아기상어3
    from collections import deque
    import sys

    # 아기상어는 상하좌우로 움직일 수 있습니다.
    dxys= [[0,-1],[-1,0],[0,1],[1,0]]

    # 격자의 크기와 아기상어와 물고기, 빈칸의 위치를 입력받습니다.
    N = int(input())
    grid = []
    for _ in range(N):
        grid.append(list(map(int, sys.stdin.readline().split())))

    # 아기상어의 초기 위치를 0으로 설정합니다. 추후에 이동할 때 상어가 지나가지 못하는 길이라 인식하는 것을 방지하기 위함입니다.
    for i in range(N):
        for j in range(N):
            if grid[i][j] == 9:
                shark_x = j
                shark_y = i
                grid[i][j] = 0

    # bfs를 이용하여 먹을 수 있는 물고기의 위치를 파악합니다.
    def bfs(s_x, s_y):
        queue = deque([])
        queue.append([s_x, s_y])
        # 방문 표시 겸 거리계산을 할 수 있게 해주는 2차원 리스트
        visited = [[0 for _ in range(N)] for _ in range(N)]
        visited[s_y][s_x] = 1
        # 먹을 수 있는 물고기까지의 거리 최솟값
        min_dis = sys.maxsize
        # 먹을 수 있는 물고기 후보군
        cand = []
        while queue:
            c_x, c_y = queue.popleft()
            for dx, dy in dxys:
                n_x = c_x + dx
                n_y = c_y + dy
                if 0 <= n_x < N and 0 <= n_y < N and grid[n_y][n_x] <= size and visited[n_y][n_x] == 0:
                    visited[n_y][n_x] = visited[c_y][c_x] + 1
                    queue.append([n_x, n_y])
                    if 0 < grid[n_y][n_x] < size and min_dis >= visited[n_y][n_x]:
                        min_dis = visited[n_y][n_x]
                        cand.append([min_dis-1, n_y, n_x])
        return sorted(cand)

    # 상어의 사이즈, 상어가 먹은 물고기 개수, 전체적으로 걸린 시간          
    size = 2
    eaten_fish = 0
    total_time = 0
                
    while 1:
        fish_loc = bfs(shark_x, shark_y)
        if fish_loc:
            # 정렬된 fish_loc에서 맨앞에 있는 리스트가 아기상어가 먹을 수 있는 물고기 중 가장 조건에 부합하는 물고기이다.
            time, shark_y, shark_x = fish_loc[0]
            grid[shark_y][shark_x] = 0
            total_time += time
            eaten_fish += 1
        else:
            break
        # 물고기를 아기상어의 사이즈만큼 먹었다면 사이즈가 1증가하며 먹은 물고기의 개수는 0으로 초기화된다.
        if eaten_fish == size:
            size += 1
            eaten_fish= 0
            
    print(total_time)

출력결과