[백준/파이썬] 16236번 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 16236번 문제
- 문제풀이 코드 GitHub 링크
- 제출 언어: Python 3
풀이
문제
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.
아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.
아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. …
입력 요약
첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.
둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.
-
0: 빈 칸
-
1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
-
9: 아기 상어의 위치
아기 상어는 공간에 한 마리 있다.
출력 요약
첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.
코드
import sys; read=sys.stdin.readline
import collections
n = int(read())
fishes = [list(map(int, read().split())) for _ in range(n)]
q = collections.deque([])
enQ = q.append
deQ = q.popleft
directions = [(-1, 0), (0, -1), (0, 1), (1, 0)]
for i in range(n):
for j in range(n):
if fishes[i][j] == 9:
fishes[i][j] = 0
shark = (i, j, 0)
size, eat, time = 2, 0, 0
while shark != (-1, -1, -1):
q.clear()
enQ(shark)
visited = [[False] * n for _ in range(n)]
visited[shark[0]][shark[1]] = True
## print('=======')
## print(f'size: {size}, eat: {eat}, time: {time}, last eat: {shark}')
## for row in fishes:
## print(*row)
## print('=======')
shark = (-1, -1, -1)
eatInfo = (-1, -1, 999_999)
while q:
current = deQ()
for direction in directions:
i, j, dt = current[0] + direction[0], current[1] + direction[1], current[2] + 1
if not(0 <= i < n) or not(0 <= j < n) or\
dt > eatInfo[2] or visited[i][j]: continue
if 0 <= fishes[i][j] <= size:
if 0 < fishes[i][j] < size:
if dt < eatInfo[2] or\
eatInfo[0] > i or\
(eatInfo[0] == i and eatInfo[1] > j):
eatInfo = (i, j, dt)
else:
enQ((i, j, dt))
visited[i][j] = True
if eatInfo[0] > -1 and eatInfo[1] > -1:
i, j, time = eatInfo[0], eatInfo[1], time + eatInfo[2]
shark = (i, j, 0)
fishes[i][j] = 0
eat += 1
if eat == size:
size += 1
eat = 0
print(time)
설명
핵심은 구현 관점에서 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.
아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. …를 만족하도록 로직을 구성하는 것입니다.
코드는 입력을 파싱한 뒤 조건 분기와 계산을 순서대로 수행하고, 문제에서 요구한 형식으로 결과를 출력합니다.
경계값과 예외 케이스도 함께 고려해 오답이 나기 쉬운 상황을 방지합니다.
댓글남기기