N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.
아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.
아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.
아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.
아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.
아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.
공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.
첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.
둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.
아기 상어는 공간에 한 마리 있다.
입력 | 출력 |
---|
| 3
0 0 0
0 0 0
0 9 0 | 0 |
| 3
0 0 1
0 0 0
0 9 0 | 3 |
| 4
4 3 2 1
0 0 0 0
0 0 9 0
1 2 3 4 | 14 |
| 6
5 4 3 2 3 4
4 3 2 3 4 5
3 2 9 5 6 6
2 1 2 3 4 5
3 2 1 6 5 4
6 6 6 6 6 6 | 60 |
| 6
6 0 6 0 6 1
0 0 0 0 0 2
2 3 4 5 6 6
0 0 0 0 0 2
0 2 0 0 0 0
3 9 3 0 0 1 | 48 |
| 6
1 1 1 1 1 1
2 2 6 2 2 3
2 2 5 2 2 3
2 2 2 4 6 3
0 0 0 0 0 6
0 0 0 0 0 9 | 39 |
최소 거리 탐색을 위해 bfs 알고리즘 필요
상어의 위치를 기준으로 먹이의 좌표, 거리를 담은 리스트를 정렬해서 사용
상어의 위치가 바뀔 때마다 탐색 알고리즘 한 번씩 필요
import sys
from collections import deque
input = sys.stdin.readline
n = int(input()) # 보드 크기
board = []
for _ in range(n):
board.append((list(map(int, input().split()))))
shark_x, shark_y, shark_size = 0, 0, 2
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# 아기 상어의 위치 찾기
for i in range(n):
for j in range(n):
if board[i][j] == 9:
board[i][j] = 0
shark_x, shark_y = i, j
def find_fish(x, y, shark_size):
fishes = []
q = deque()
visited = [[0] * n for _ in range(n)]
distance = [[0] * n for _ in range(n)]
q.append((x, y))
visited[x][y] = 1
while q:
x, y = q.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0:
if board[nx][ny] <= shark_size: # 이동이 가능할 때
q.append((nx, ny))
visited[nx][ny] = 1
distance[nx][ny] = distance[x][y] + 1
if board[nx][ny] < shark_size and board[nx][ny] != 0: # 먹을 수 있을 때
fishes.append([nx, ny, distance[nx][ny]])
fishes.sort(key = lambda x: (x[2], x[0], x[1]))
return fishes
eat, result = 0, 0
while 1:
fishes = find_fish(shark_x, shark_y, shark_size)
if len(fishes) == 0: # 먹을 수 있는 물고기가 없으면 종료
print(result)
break
else:
shark_x, shark_y, dis = fishes[0]
eat += 1 # 몇 마리 먹었는지 기록
board[shark_x][shark_y] = 0 # 먹은 곳은 보드 제거
result += dis
if (eat == shark_size):
shark_size += 1
eat = 0
처음에 예제 코드 4, 5가 자꾸 오류가 떴는데 아기 상어의 위치를 찾을 때 아기 상어가 위치한 곳에 먹이가 없다고 0으로 표기하는 것을 까먹었었다. 이를 수정하니 코드가 통과했다.
# 아기 상어의 위치 찾기
for i in range(n):
for j in range(n):
if board[i][j] == 9:
board[i][j] = 0 # <--- 까먹음
shark_x, shark_y = i, j