https://www.acmicpc.net/problem/17836
시간 1초, 메모리 256MB
input :
- N M T(3 ≤ N, M ≤ 100, 1 ≤ T ≤ 10000)
- 성의 구조를 나타내는 M개의 수 (0은 빈 공간, 1은 마법의 벽, 2는 그람이 놓여있는 공간을 의미한다. (1,1)과 (N,M)은 0)
output :
- T시간 이내에 공주에게 도달할 수 있다면, 공주에게 도달할 수 있는 최단 시간을 출력
- T시간 이내에 구출할 수 없다면, "Fail"을 출력
조건 :
- 용사가 그람을 구하면 마법의 벽이 있는 칸일지라도, 단숨에 벽을 부수고 그 공간으로 갈 수 있다
- 반드시 한 개 존재하고, 용사는 그람이 있는 곳에 도착하면 바로 사용할 수 있다. 그람이 부술 수 있는 벽의 개수는 제한이 없다.
메모리 초과가 문제였다.
큐에 많은 정보를 집어넣는 것은 좋지 않은 습관 인 것을 겪었다.
처음 4가지의 정보를 집어 넣으려 했다. x, y, gram, time 이 네가지를 집어넣으니 바로 메모리 초과가 발생 했다. 배열의 크기는 100 * 100 으로 별로 크지 않지만 큐에 쌓이는 좌표가 메모리를 많이 먹는 듯 하다.
visit 배열에 시간을 저장 하도록 하고, 큐는 좌표만을 저장하도록 하니 괜찮아 졌다.
생각해야 할 부분은 그람을 주웠을 때 그 자리에서 도착 지점까지의 거리가 최단 거리라는 것이다.
그래서 visit[nx][ny] 값을 업데이트 한 후에 도착 지점 n - 1, m - 1 에서 nx, ny 까지의 값을 더한 것이 최단 거리가 된다.
그리고 이 경우 외에 BFS를 수행해서 도착이 가능 하다면 ret 값을 비교해서 return 하도록 한다.
공주를 만나지 못하는 경우도 존재하므로 ret 값을 리턴 하도록 해야 한다.
import sys
from collections import deque
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs():
ret = 10001
q = deque([(0, 0)])
visit[0][0] = 0
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx == n - 1 and ny == m - 1:
return min(ret, visit[x][y] + 1)
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if graph[nx][ny] == 0 and visit[nx][ny] == 0:
visit[nx][ny] = visit[x][y] + 1
q.append((nx, ny))
elif graph[nx][ny] == 2 and visit[nx][ny] == 0:
visit[nx][ny] = visit[x][y] + 1
ret = min(ret, visit[nx][ny] + abs(n - 1 - nx) + abs(m - 1 - ny))
return ret
n, m, t = map(int, sys.stdin.readline().split())
graph = []
for i in range(n):
graph.append(list(map(int, sys.stdin.readline().split())))
visit = [[0] * m for i in range(n)]
ans = bfs()
print("Fail" if ans > t else ans)
