| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 65790 | 30563 | 18549 | 43.050% |
문제
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: 아기 상어의 위치
아기 상어는 공간에 한 마리 있다.
출력
첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.
답안
import heapq
import sys
# initialize variables
SHARK = 9
table_size = int(sys.stdin.readline())
table = []
start = None
# initialize table
for i in range(table_size):
table.append(list(map(int, sys.stdin.readline().split())))
# find start point during initializing table
for j, elem in enumerate(table[-1]):
if elem == SHARK:
start = (i, j)
table[-1][j] = 0
def bfs(target, start, visited):
queue = [(0, start)]
# queue is sorted by these rules:
# 1. the nearest cell (has the least move counts value)
# 2. with the lowest row value
# 3. with the lowest column value
deltas = [(-1, 0), (0, -1), (0, 1), (1, 0)]
while queue:
(move_counts, (row, col)) = heapq.heappop(queue)
# if cell is not empty(0) and the shark can eat the fish in the cell
if 0 < table[row][col] < target:
table[row][col] = 0
queue = []
return (move_counts, (row, col))
for d_row, d_col in deltas:
n_row, n_col = row+d_row, col+d_col
is_valid_coordinate = 0 <= n_row < table_size and 0 <= n_col < table_size
if is_valid_coordinate and not visited[n_row][n_col]:
visited[n_row][n_col] = True
heapq.heappush(queue, (move_counts+1, (n_row, n_col)))
return (None, (None, None))
def solve(start):
size = 2
size_upgrade_stack = 0
answer = 0
while True:
# in order the size be grown, the stack should be equal to the shark's size
if size_upgrade_stack == size:
size_upgrade_stack = 0
size += 1
# re-initialize visited variable.
# if the cells in the table has higher value than the shark's size,
# the shark cannot pass through the cell.
# so you make the cell status as 'visited.'
visited = [[False] * table_size for _ in range(table_size)]
visited[start[0]][start[1]] = True
for i in range(table_size):
for j in range(table_size):
if table[i][j] > size:
visited[i][j] = True
move_counts, (row, col) = bfs(size, start, visited)
if move_counts == None:
return answer
start = (row, col)
answer += move_counts
size_upgrade_stack += 1
answer = solve(start)
print(answer)풀이
이 문제를 풀려면 최단 경로를 여러 번 구해야만 한다.
- 처음의 상어 위치로부터,
- 가장 가까운 먹이(상어의 크기보다 작은 크기를 가진 물고기)까지,
- 그리고 그 먹이 위치로부터 가장 가까운 먹이까지,
- … (더 먹을 먹이가 없을 때까지 반복)
이때 최단경로를 구할 때마다 상어의 크기에 따라 지나다닐 수 있는 장소와 먹을 수 있는 먹이가 계속 달라지기 때문에 이전의 결과를 재사용해서 processing time을 줄이는 것이 어려워 보인다.
마침 문제에서 주어진 공간의 크기가 길이가 n(1 ≤ n ≤ 20)인 정사각형이니, 400개의 블럭을 대상으로 탐색하는 알고리즘을 여러 번 돌리더라도 문제 풀이가 가능할 것 같다.
그래서 나는 BFS를 여러 번 돌림으로써 이 문제를 풀어보기로 했다.
BFS
def bfs(target, start, visited):
queue = [(0, start)]
# queue is sorted by these rules:
# 1. the nearest cell (has the least move counts value)
# 2. with the lowest row value
# 3. with the lowest column value
deltas = [(-1, 0), (0, -1), (0, 1), (1, 0)]
while queue:
(move_counts, (row, col)) = heapq.heappop(queue)
...bfs()에서는 현재 위치로부터 가장 가까운 먹이의 위치를 찾아, 만약 먹이를 찾았다면 현재 위치부터 그 먹이까지의 거리를 return한다.
이때, 문제 조건에서
거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
라는 조건이 있는데, 이는 priority queue에 들어가는 cell 정보들의 sort 조건이 다음과 같아야 한다는 것이다.
- 현재 상어 위치로부터 거리가 가장 가까운 것
- 가장 위에 있는 것 (즉, 가장 row 값이 작은 것)
- 가장 왼쪽에 있는 것 (즉, 가장 col 값이 작은 것)
python에서의 heapq는 min heap으로 구현되어 있어, heappop()을 하게 되면 값이 가장 낮은 것부터 pop된다. 만약 iterable한 객체인 경우 그 다음 순서의 요소를 비교해 그 값이 낮은 것을 pop한다.
따라서 priority queue에 들어가는 요소 정보를 (현재 상어 위치로부터의 거리, (row 값, column 값))과 같이 설계하면 문제의 조건들을 만족시킬 수 있는 것이다.
주의할 점: 상어의 크기
그리고 이 문제에서 주의해야 하는 것들 중 하나로, 상어의 크기가 있다.
def solve(start):
size = 2
size_upgrade_stack = 0
answer = 0solve()에서는 상어의 크기와, 상어의 크기가 늘어난 후부터 먹은 먹이의 수를 저장해놓는다.
# in order the size be grown, the stack should be equal to the shark's size
if size_upgrade_stack == size:
size_upgrade_stack = 0
size += 1bfs()를 한 번 실행해 정상적으로 종료했다면 상어가 먹이를 한 번 먹은 것이므로, 먹이를 먹을 때마다 위와 같이 상어의 크기를 키울지 말지를 결정한다.
문제 조건에 따라, 먹이를 먹은 횟수가 상어 자신의 크기와 같다면 상어의 크기가 1 커진다.
# re-initialize visited variable.
# if the cells in the table has higher value than the shark's size,
# the shark cannot pass through the cell.
# so you make the cell status as 'visited.'
visited = [[False] * table_size for _ in range(table_size)]
visited[start[0]][start[1]] = True
for i in range(table_size):
for j in range(table_size):
if table[i][j] > size:
visited[i][j] = True상어의 크기에 따라 상어가 지나갈 수 있는 길이 달라지기 때문에, 이를 위해 먹이를 먹을 때마다 visited 배열을 다시 만들어줘야 한다.
상어가 지나다닐 수 있는 길은, 비어있거나(0) 자신보다 크기가 작거나 같은 물고기(0 ~ size)이고, 상어의 크기보다 더 큰 물고기들을 지나가지 못하게 하기 위해 해당 물고기가 있는 위치를 visited된 상태로 만들어버린다.
def bfs(target, start, visited):
while queue:
...
...
return (None, (None, None))
def solve(start):
...
move_counts, (row, col) = bfs(size, start, visited)
if move_counts == None:
return answer
answer = solve(start)
print(answer)queue를 모두 돌고 나서도 자신의 크기보다 작은 물고기를 찾지 못하는 경우에는 (None, (None, None))을 return하게 되고, 이 경우 가장 마지막 라운드에 최단 경로를 찾기 위해 지나왔던 거리들을 무효로 하고 answer를 반환한다.
이렇게 일반적인 BFS를 여러 번 돌리되, BFS에 사용되는 priority queue 내부 설계와 상어의 크기에 따른 변경점들을 잘 고려하여 문제를 풀면 된다.
