https://www.acmicpc.net/problem/4485
시간 1초, 메모리 256MB
input :
- N (2 ≤ N ≤ 125)
- 도둑루피의 크기가 공백으로 구분
output :
- 테스트 케이스마다 한 줄에 걸쳐 정답을 형식에 맞춰서 출력
조건 :
-
링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다.
-
제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동
-
이 칸을 지나면 해당 도둑루피의 크기만큼 소지금을 잃게 된다.
-
잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동
A star 또는 다익스트라를 사용해야 할 것 같다.
기본적인 다익스트라 코드를 사용하는데 초반에 입력을 받았을 때를 대비해 조건을 걸어야 한다.
visit을 통해 해당 칸 까지 이동을 했을 때 잃게 되는 루비를 저장하게 하자.
그렇게 해서 다익스트라를 이용해서 찾아갔을 때 현재까지 잃은 루비와 비교를 하도록 한다.
힙을 사용해서 이걸 좀 더 쉽게 찾을 수 있을 것 같다.
import sys
from heapq import heappush, heappop
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
cnt = 1
while True:
n = int(sys.stdin.readline())
if n == 0:
break
graph, visit = [], [[float('inf')] * n for _ in range(n)]
for _ in range(n):
temp = list(map(int, sys.stdin.readline().split()))
graph.append(temp)
q = []
visit[0][0] = graph[0][0]
heappush(q, (graph[0][0], 0, 0))
while q:
cost, x, y = heappop(q)
if cost > visit[x][y]:
continue
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if visit[nx][ny] > cost + graph[nx][ny]:
heappush(q, (cost + graph[nx][ny], nx, ny))
visit[nx][ny] = cost + graph[nx][ny]
print(f"Problem {cnt}: {visit[n - 1][n - 1]}")
cnt += 1
현재까진 예제가 좀 약해서 예전 코드가 맞았던 거 같다. x, y가 도착 지점에 왔다고 해서 이게 제일 적게 잃은게 아닐 수도 있기 때문에 이 부분을 다시 보완했다.
