728x90
문제 설명
N×N 크기의 공간에 아기 상어와 여러 물고기가 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있고, 자신보다 큰 물고기가 있는 칸은 지나갈 수 없다. 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가한다.
아기 상어는 먹을 수 있는 물고기가 여러 마리일 경우, 다음의 우선순위로 이동한다:
- 가장 가까운 물고기를 먹으러 간다 (이동 칸 수가 최소인 물고기).
- 거리가 가까운 물고기가 여러 마리라면, 가장 위에 있는 물고기를 먹는다.
- 그러한 물고기가 여러 마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
아기 상어가 더 이상 먹을 수 있는 물고기가 없을 때까지 이동하면서 물고기를 먹었을 때, 걸리는 시간을 구하는 것이 문제의 목표다.
문제 접근
이 문제는 BFS(너비 우선 탐색)를 활용하여 해결할 수 있다. BFS를 사용하여 아기 상어로부터의 거리를 계산하고, 먹을 수 있는 물고기 중에서 우선순위에 따라 선택하면 된다.
알고리즘 단계
- 초기 설정:
- 공간의 상태를 입력받고, 아기 상어의 위치와 초기 크기를 설정한다.
- 상어의 현재 위치에서 BFS를 시작한다.
- BFS 탐색:
- 큐를 사용하여 상어의 이동 가능한 위치를 탐색한다.
- 이동하면서 거리를 계산하고, 먹을 수 있는 물고기를 찾는다.
- 먹을 물고기 선택:
- 먹을 수 있는 물고기 목록 중에서 우선순위에 따라 선택한다.
- 가장 가까운 거리
- 가장 위에 있는 물고기 (행 번호가 작은 것)
- 가장 왼쪽에 있는 물고기 (열 번호가 작은 것)
- 먹을 수 있는 물고기 목록 중에서 우선순위에 따라 선택한다.
- 상어 이동 및 상태 업데이트:
- 선택한 물고기의 위치로 상어를 이동시키고, 시간을 누적한다.
- 상어가 물고기를 먹은 횟수를 증가시키고, 크기 변화가 필요한지 확인한다.
- 공간 상태를 업데이트한다.
- 반복:
- 더 이상 먹을 수 있는 물고기가 없을 때까지 위의 과정을 반복한다.
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를 사용하여 상어의 현재 위치에서 모든 가능한 위치로의 거리를 계산하고, 먹을 수 있는 물고기를 찾는다.
- 우선순위에 따른 물고기 선택: 먹을 수 있는 물고기가 여러 마리일 경우, 문제에서 제시한 우선순위(거리, 행, 열)에 따라 물고기를 선택한다.
- 상어의 상태 관리: 상어의 크기와 먹은 물고기 수를 관리하여 크기 증가 조건을 정확히 구현한다.
도움이 되셨다면 공감과 댓글 부탁드립니다.
728x90
'Python > 백준' 카테고리의 다른 글
백준 낚시왕 [17143] 파이썬(Python) 코드 + 해설 (0) | 2024.11.04 |
---|---|
백준 미세먼지 안녕! [17144] 파이썬(Python) 코드 + 해설 (0) | 2024.11.03 |
백준 나무 재테크 [16325] 파이썬(Python) 코드 + 해설 (2) | 2024.11.02 |
백준 인구이동 [16324] 파이썬(Python) 코드 + 해설 (0) | 2024.11.01 |
백준 큐빙 [5373] 파이썬(Python) 코드 + 해설 (0) | 2024.11.01 |