백준 아기 상어 [16326] 파이썬(Python) 코드 + 해설

백준 아기상어 16326 문제

문제 설명

N×N 크기의 공간에 아기 상어와 여러 물고기가 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있고, 자신보다 큰 물고기가 있는 칸은 지나갈 수 없다. 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가한다.

아기 상어는 먹을 수 있는 물고기가 여러 마리일 경우, 다음의 우선순위로 이동한다:

1. 가장 가까운 물고기를 먹으러 간다 (이동 칸 수가 최소인 물고기).
2. 거리가 가까운 물고기가 여러 마리라면, 가장 위에 있는 물고기를 먹는다.
3. 그러한 물고기가 여러 마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어가 더 이상 먹을 수 있는 물고기가 없을 때까지 이동하면서 물고기를 먹었을 때, 걸리는 시간을 구하는 것이 문제의 목표다.

문제 접근

이 문제는 BFS(너비 우선 탐색)를 활용하여 해결할 수 있다. BFS를 사용하여 아기 상어로부터의 거리를 계산하고, 먹을 수 있는 물고기 중에서 우선순위에 따라 선택하면 된다.

알고리즘 단계

1. 초기 설정:
   • 공간의 상태를 입력받고, 아기 상어의 위치와 초기 크기를 설정한다.
   • 상어의 현재 위치에서 BFS를 시작한다.
2. BFS 탐색:
   • 큐를 사용하여 상어의 이동 가능한 위치를 탐색한다.
   • 이동하면서 거리를 계산하고, 먹을 수 있는 물고기를 찾는다.
3. 먹을 물고기 선택:
   • 먹을 수 있는 물고기 목록 중에서 우선순위에 따라 선택한다.
     • 가장 가까운 거리
     • 가장 위에 있는 물고기 (행 번호가 작은 것)
     • 가장 왼쪽에 있는 물고기 (열 번호가 작은 것)
4. 상어 이동 및 상태 업데이트:
   • 선택한 물고기의 위치로 상어를 이동시키고, 시간을 누적한다.
   • 상어가 물고기를 먹은 횟수를 증가시키고, 크기 변화가 필요한지 확인한다.
   • 공간 상태를 업데이트한다.
5. 반복:
   • 더 이상 먹을 수 있는 물고기가 없을 때까지 위의 과정을 반복한다.

16326 아기상어 파이썬(Python)  정답 코드

import sys
from collections import deque

input = sys.stdin.readline

# 입력 받기
N = int(input())
space = [list(map(int, input().split())) for _ in range(N)]

# 아기 상어의 초기 위치와 크기 설정
for i in range(N):
    for j in range(N):
        if space[i][j] == 9:
            shark_x, shark_y = i, j
            space[i][j] = 0  # 상어의 현재 위치를 빈 공간으로 변경
            break

# 방향 설정 (상, 좌, 우, 하)
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

# 아기 상어의 상태
shark_size = 2
shark_eat = 0
time = 0

def bfs(x, y, size):
    visited = [[-1]*N for _ in range(N)]
    queue = deque()
    queue.append((x, y))
    visited[x][y] = 0
    fishes = []

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == -1:
                # 상어가 지나갈 수 있는 경우
                if space[nx][ny] <= size:
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append((nx, ny))
                    # 먹을 수 있는 물고기인 경우
                    if 0 < space[nx][ny] < size:
                        fishes.append((visited[nx][ny], nx, ny))

    # 먹을 수 있는 물고기가 있는 경우
    if fishes:
        fishes.sort()
        return fishes[0]  # 가장 우선순위가 높은 물고기 반환
    else:
        return None

while True:
    result = bfs(shark_x, shark_y, shark_size)
    if result is None:
        break  # 더 이상 먹을 수 있는 물고기가 없음
    else:
        dist, x, y = result
        time += dist  # 이동 시간 누적
        shark_x, shark_y = x, y  # 상어 위치 이동
        space[x][y] = 0  # 물고기를 먹은 위치는 빈 칸으로 변경
        shark_eat += 1  # 먹은 물고기 수 증가

        # 상어의 크기 증가 조건 확인
        if shark_eat == shark_size:
            shark_size += 1
            shark_eat = 0

print(time)

 

문제 해결 방법

• BFS를 활용한 최단 거리 탐색: BFS를 사용하여 상어의 현재 위치에서 모든 가능한 위치로의 거리를 계산하고, 먹을 수 있는 물고기를 찾는다.
• 우선순위에 따른 물고기 선택: 먹을 수 있는 물고기가 여러 마리일 경우, 문제에서 제시한 우선순위(거리, 행, 열)에 따라 물고기를 선택한다.
• 상어의 상태 관리: 상어의 크기와 먹은 물고기 수를 관리하여 크기 증가 조건을 정확히 구현한다.

 

백준 16326 아기 상어 제출 결과

 

도움이 되셨다면 공감과 댓글 부탁드립니다.