💡 문제
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.
아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.
아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.
아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.
- 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
- 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
- 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
- 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
- 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
- 아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.
아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.
공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.
둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.
- 0: 빈 칸
- 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
- 9: 아기 상어의 위치
아기 상어는 공간에 한 마리 있다.
출력
첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.
💭 접근
이 문제를 해결하기 위해 다음과 같은 순서로 구현하였다.
-
현재 아기 상어의 위치에서 먹을 수 있는 물고기 구하기
def bfs(): q = deque() q.append((shark_x, shark_y)) visited = [[0 for _ in range(n)] for _ in range(n)] fish = [] while q: x, y = q.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] == 0: # 이동 가능한 물고기 중 먹을 수 있는 물고기라면 if 0 < graph[nx][ny] < size[0]: visited[nx][ny] = visited[x][y] + 1 q.append((nx, ny)) fish.append([visited[nx][ny], nx, ny]) # 먹을 수 있는 물고기 리스트에 append # 빈칸이거나 같은 크기의 물고기가 있다면 elif graph[nx][ny] == 0 or graph[nx][ny] == size[0]: visited[nx][ny] = visited[x][y] + 1 # 방문처리만 q.append((nx, ny)) return sorted(fish, key=lambda x : (x[0], x[1], x[2])) # 먹을 물고기의 우선순위 fish = deque(bfs())위 코드와 같이
bfs함수를 호출하여 현재 아기 상어의 위치를 기준으로 비어있는 공간이거나 자신과 크기가 같은 물고기라면 그냥 지나가고, 자신보다 크기가 작은 물고기가 있다면fish리스트에 추가한다.이후, 문제에서 주어진 조건에 따라
fish리스트를 정렬한다. -
먹을 수 있는 물고기가 없다면 종료
if not fish: break # 더 이상 먹을 수 있는 물고기가 없으면 breakbfs함수로 물고기 탐색이 끝난 후, 먹을 수 있는 물고기가 없다면 종료하고 정답을 출력한다. -
먹을 수 있는 물고기가 있다면 아기 상어의 크기를 갱신하고 이동시간을 더하고 아기 상어를 그 위치로 이동
cnt, x, y = fish.popleft() graph[x][y] = 0 # 물고기를 잡아 먹었으므로 빈칸 ans += cnt # 물고기를 잡아먹는데에 걸리는 시간 + size[1] += 1 if size[0] == size[1]: # 상어의 크기 갱신 size[0] += 1 size[1] = 0 graph[shark_x][shark_y] = 0 # 물고기가 있는 위치로 상어가 이동했으므로 빈칸 shark_x, shark_y = x, y # 상어의 좌표 갱신bfs함수로 물고기 탐색이 끝난 후 먹을 수 있는 물고기가 있다면 조건에 가장 부합하는 물고기를 잡아먹고, 아기 상어의 크기와 좌표를 갱신한다.
위와 같은 순서로 더 이상 먹을 수 있는 물고기가 없을 때까지 반복한다.
📒 코드
from collections import deque
def bfs():
q = deque()
q.append((shark_x, shark_y))
visited = [[0 for _ in range(n)] for _ in range(n)]
fish = []
while q:
x, y = q.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] == 0:
# 이동 가능한 물고기 중 먹을 수 있는 물고기라면
if 0 < graph[nx][ny] < size[0]:
visited[nx][ny] = visited[x][y] + 1
q.append((nx, ny))
fish.append([visited[nx][ny], nx, ny]) # 먹을 수 있는 물고기 리스트에 append
# 빈칸이거나 같은 크기의 물고기가 있다면
elif graph[nx][ny] == 0 or graph[nx][ny] == size[0]:
visited[nx][ny] = visited[x][y] + 1 # 방문처리만
q.append((nx, ny))
return sorted(fish, key=lambda x : (x[0], x[1], x[2])) # 먹을 물고기의 우선순위
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
for j in range(n):
if graph[i][j] == 9:
shark_x, shark_y = i, j
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
ans = 0
size = [2, 0]
while True:
fish = deque(bfs())
if not fish: break # 더 이상 먹을 수 있는 물고기가 없으면 break
cnt, x, y = fish.popleft()
graph[x][y] = 0 # 물고기를 잡아 먹었으므로 빈칸
ans += cnt # 물고기를 잡아먹는데에 걸리는 시간 +
size[1] += 1
if size[0] == size[1]: # 상어의 크기 갱신
size[0] += 1
size[1] = 0
graph[shark_x][shark_y] = 0 # 물고기가 있는 위치로 상어가 이동했으므로 빈칸
shark_x, shark_y = x, y # 상어의 좌표 갱신
print(ans)💭 후기
list를 정렬할 때 sort()와 sorted를 사용할 수 있는데 아래와 같이 내가 원하는 조건에 따라 정렬할 수 있는 방법을 배울 수 있었다.
sorted(fish, key=lambda x : (x[0], x[1], x[2]))🔗 문제 출처
https://www.acmicpc.net/problem/16236
