메모리: 33992 KB, 시간: 184 ms
너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal), 구현(implementation), 시뮬레이션(simulation)
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로 이루어져 있고, 아래와 같은 의미를 가진다.
아기 상어는 공간에 한 마리 있다.
첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.
문제를 잘못 읽은 부분이 많았어서, 그 부분들을 고치느라 문제푸는데 시간이 정말 오래 걸렸다.
먼저 BFS를 통해 현재 위치에서 먹을 수 있는 물고기가 있는 위치에서 가장 적은 시간이 걸리는 물고기들만 찾았다.
이때 heapq를 사용했다! heapq에 이동 시간, 행, 열 순으로 넣어서 문제에서 제시한 위쪽, 왼쪽 순서대로 찾도록 했다.
그리고 현재 내가 먹은 물고기의 수를 비교하면서, 크기를 늘려주었다.
import sys
from collections import deque
import heapq
N = int(sys.stdin.readline())
MAP = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]
size = 2
cnt = 0
def BFS(st, sr, sc) :
global size, cnt
visited = [[0 for _ in range(N)] for _ in range(N)]
visited[sr][sc] = 1
queue = deque()
queue.append((st, sr, sc))
area = []
minT = 1e9
while queue :
t, r, c = queue.popleft()
for i in range(4) :
nt, nr, nc = t + 1, r + dr[i], c + dc[i]
if nr < 0 or nr >= N or nc < 0 or nc >= N or visited[nr][nc] == 1 :
continue
if size >= MAP[nr][nc] :
if 0 < MAP[nr][nc] < size :
if nt > minT :
break
else :
minT = nt
heapq.heappush(area, (nt, nr, nc))
else :
queue.append((nt, nr, nc))
visited[nr][nc] = 1
if area :
newT, newR, newC = heapq.heappop(area)
MAP[sr][sc] = 0
MAP[newR][newC] = 9
cnt += 1
if size == cnt :
size += 1
cnt = 0
BFS(newT, newR, newC)
else :
print(st)
for i in range(N) :
for j in range(N) :
if MAP[i][j] == 9 :
BFS(0, i, j)
break
else:
continue
break