[백준 - 16236] 아기 상어
문제
문제링크
공간은 N (2 <= N <= 20)
아기 상어는 9
물고기 크기는 1~6
아기 상어는 자신의 크기보다 작은 크기의 물고기를 먼저 먹는다.
문제풀이
아기상어는 먹을 수 있는 물고기 중에서 가장 가까운 물고기를 먼저 먹는다. 이점을 활용해 먹을 수 있는 물고기 중 가장 가까운 거리에 있는 것을 선택한다.
BFS를 통해 접근하며 자료형은 queue를 활용한다. 이후 잡아 먹을 수 있는 물고기가 없다면 끝낸다.
from collections import deque
INF = 1e9 # 무한을 의미하는 값 10억을 설정
# 맵의 크기 N
n = int(input())
# 전체 모든 칸에 대한 정보 입력
array = []
for i in range(n):
array.append(list(map(int, input().split())))
# 아기 상어의 현재 크기 변수와 현재 위치 변수
now_size = 2
nox_x, now_y = 0, 0
# 아기 상어의 시작 위치를 찾은 뒤에 그 위치엔 아무것도 없다고 처리
for i in range(n):
for j in range(n):
if array[i][j] == 9:
now_x, now_y = i, j
array[now_x][now_y] = 0
# 북 동 남 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# 모든 위치까지의 '최단 거리만' 계산하는 BFS 함수
def bfs():
# 값이 -1이라면 도달할 수 없다는 의미(초기화)
dist = [[-1] * n for _ in range(n)]
# 시작 위치는 도달이 가능하다고 보며 거리는 0
q = deque([(now_x, now_y)])
dist[now_x][now_y] = 0
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx and nx < n and 0 <= ny and ny <n :
# 자신의 크기보다 작거나 같은 경우에 지나갈 수 있음
if dist[nx][ny] == -1 and array[nx][ny] <= now_size:
dist[nx][ny] = dist[x][y] + 1
q.append((nx, ny))
# 모든 위치까지의 최단 거리 테이블 반환
return dist
# 최단 거리 테이블이 주어졌을 때, 먹을 물고기를 찾는 함수
def find(dist):
x, y = 0, 0
min_dist = INF
for i in range(n):
for j in range(n):
# 도달이 가능하면서 먹을 수 있는 물고기일 때
if dist[i][j] != -1 and 1 <= array[i][j] and array[i][j] < now_size:
# 가장 가까운 물고기 1마리만 선택
if dist[i][j] < min_dist:
x, y = i, j
min_dist = dist[i][j]
if min_dist == INF: # 먹을 수 있는 물고기가 없는 경우
return None
else :
return x, y, min_dist # 먹을 물고기의 위치와 최단거리
result = 0 # 최종 답안
ate = 0 # 현재 크기에서 먹을 수 있는 양
while True:
# 먹을 수 있는 물고기의 위치 찾기
value = find(bfs())
# 먹을 수 있는 물고기가 없는 경우, 현재까지 움직인 거리 출력
if value == None:
print(result)
break
else :
# 현재 위치 갱신 및 이동 거리 변경
now_x, now_y = value[0], value[1]
result += value[2]
# 먹은 위치에는 이제 아무것도 없도록 처리
array[now_x][now_y] = 0
ate += 1
# 자신의 현재 크기 이상으로 먹은 경우, 크기 증가
if ate >= now_size:
now_size += 1
ate = 0
아쉬운 점
구현 부분에서 깔끔하게 구현하는 연습을 하자.
먼저 구체적으로 해보고 난 뒤, 함수화를 통해 알기 쉽게 표현하자
해당 문서는 '이것이 코딩 테스트다. with 파이썬 - 나동빈 저'를 읽고 공부한 글입니다.
Author And Source
이 문제에 관하여([백준 - 16236] 아기 상어), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@koyo/boj-16236저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)