python 16236 아기상어

 

 

문제 분석

1. 게임판: N x N 크기의 공간에서 아기 상어(크기 2)가 이동하면서 물고기를 잡아먹음.
2. 이동 규칙:
   • 상어는 자신의 크기보다 작은 물고기만 먹을 수 있음.
   • 이동 시 거리가 가장 가까운 물고기를 먹음 (BFS 사용).
   • 같은 거리에 여러 물고기가 있으면 가장 위쪽 → 가장 왼쪽 우선순위.
   • 물고기를 먹을 때마다 크기와 먹은 횟수를 체크하여, 크기만큼 먹으면 크기가 1 증가.
3. 결과: 아기 상어가 더 이상 먹을 물고기가 없을 때까지 걸리는 총 시간을 출력.

풀이 방법

1. BFS 탐색을 사용하여 가장 가까운 물고기 찾기.
2. 찾은 물고기를 먹고, 상어의 크기 및 먹은 횟수 갱신.
3. 더 이상 먹을 물고기가 없을 때까지 반복.

 

import sys
from collections import deque

input = sys.stdin.readline

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

def bfs(shark_x, shark_y, shark_size, grid, N):
    queue = deque([(shark_x, shark_y, 0)])
    visited = [[False] * N for _ in range(N)]
    visited[shark_x][shark_y] = True
    fish_list = []
    min_dist = float('inf')
    
    while queue:
        x, y, dist = queue.popleft()
        
        if 0 < grid[x][y] < shark_size:
            if dist < min_dist:
                fish_list = [(x, y, dist)]
                min_dist = dist
            elif dist == min_dist:
                fish_list.append((x, y, dist))
        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                if grid[nx][ny] <= shark_size:
                    queue.append((nx, ny, dist + 1))
                    visited[nx][ny] = True
    
    if fish_list:
        fish_list.sort()
        return fish_list[0]
    return None

def solve(N, grid):
    for i in range(N):
        for j in range(N):
            if grid[i][j] == 9:
                shark_x, shark_y = i, j
                grid[i][j] = 0
    
    shark_size = 2
    eat_count = 0
    total_time = 0
    
    while True:
        result = bfs(shark_x, shark_y, shark_size, grid, N)
        if not result:
            break 
        
        fish_x, fish_y, dist = result
        grid[fish_x][fish_y] = 0 
        total_time += dist
        eat_count += 1
        
        if eat_count == shark_size:
            shark_size += 1
            eat_count = 0

        shark_x, shark_y = fish_x, fish_y
    
    return total_time

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

print(solve(N, grid))

 

1. BFS를 이용한 물고기 탐색
   • bfs() 함수는 가장 가까운 물고기를 찾음.
   • 같은 거리라면 위쪽(작은 x) → 왼쪽(작은 y) 순으로 정렬하여 반환.
   • 상어보다 크기가 작은 물고기만 먹을 수 있음.
2. 메인 루프 (solve() 함수)
   • bfs()를 통해 물고기 탐색.
   • 찾은 물고기를 먹고 상어 위치 업데이트.
   • 먹은 개수만큼 크기를 갱신하고, 더 이상 먹을 수 없으면 종료.
3. 출력
   • 아기 상어가 더 이상 먹을 물고기가 없을 때까지 걸린 총 시간을 출력.