[백준] 16236번: 아기 상어
BFS 응용 문제이다. 상어의 크기가 점점 커지면서 매 탐색 시 탐색 조건이 바뀐다.
이 문제도 첫 시도를 실패했는데, 문제의 조건 중 '거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.' 를 구현할 때 착각한 것이 원인이었다.
BFS 탐색을 할 때 기준 좌표에서 위쪽, 왼쪽 순으로 이동 방향을 지정해주면 될 거라 생각했지만 (for dy, dx in [(-1, 0), (0, -1), ... ]
부분)
이 값은 탐색 중 이동하는 모든 블록 각각에 대해 적용되는 값이지, 처음 위치 기준이 아니기 때문에 처음 발견한 물고기가 같은 거리의 물고기들 중 가장 위쪽-왼쪽의 것임을 보장하지 않는다.
이 조건을 만족하기 위해서는 일단 먹을 수 있는 모든 물고기를 찾고, 그것들을 다시 한 번 거리-Y좌표-X좌표 순으로 정렬해야 한다.
import sys, copy
from collections import deque
input = sys.stdin.readline
N = int(input().rstrip())
matrix = []
coord_x, coord_y = 0, 0
for _ in range(N):
arr = list(map(int, input().split()))
if 9 in arr:
coord_y, coord_x = (_, arr.index(9))
arr[coord_x] = 0
matrix.append(arr)
def find_food(init_y, init_x, size, count):
q = deque([(init_y, init_x)])
eatable = []
visited = [[0] * N for _ in range(N)]
while q:
y, x = q.popleft()
for dy, dx in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
if (
0 <= y + dy < N
and 0 <= x + dx < N
and visited[y + dy][x + dx] == 0
and matrix[y + dy][x + dx] <= size
):
if (matrix[y + dy][x + dx] == 0 or matrix[y + dy][x + dx] == size):
q.append((y + dy, x + dx))
visited[y + dy][x + dx] = visited[y][x] + 1
elif 0 < matrix[y + dy][x + dx] < size:
visited[y + dy][x + dx] = visited[y][x] + 1
eatable.append((visited[y + dy][x + dx], y + dy, x + dx))
if len(eatable) > 0:
eatable.sort()
c, y, x = eatable[0]
matrix[y][x] = 0
return (count + c, y, x)
# 유효 범위 내에 먹이가 없을 때
return (count, -1, -1)
stomach = 2
eat = 0
count = 0
while True:
count, coord_y, coord_x = find_food(coord_y, coord_x, stomach, count)
if coord_y > -1 and coord_x > -1:
eat += 1
if eat >= stomach:
stomach += 1
eat = 0
else:
break
print(count)
Author And Source
이 문제에 관하여([백준] 16236번: 아기 상어), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@js43o/백준-16236번-아기-상어저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)