https://www.acmicpc.net/problem/4485

칸에 숫자가 있고, [0, 0]에서 [n, n]까지 가는데 숫자의 합이 최소가 되도록 하는 문제이다.

Python

1차 실패 - DP

def dpf(i, j, dp, cave, n):
  if dp[i][j] == n * n * 100:
    up = dpf(i-1, j, dp, cave, n) if i > 0 else n * n * 1000
    left = dpf(i, j-1, dp, cave, n) if j > 0 else n * n * 1000
    down = dpf(i+1, j, dp, cave, n) if i + 1 < n else n * n * 1000
    right = dpf(i, j+1, dp, cave, n) if j + 1 < n else n * n * 1000
    
    dp[i][j] = cave[i][j] + min(left, up, right, down)
    
  return dp[i][j]

count = 1
while True:
  n = int(input())
  
  if n == 0:
    break
  cave = list(list(map(int, input().split())) for _ in range(n))
  
  dp = [[n * n * 100] * n for _ in range(n)]
  dp[0][0] = cave[0][0]
  
  # 점화식
  # dp[n][n] = min(dp[n-1][n], dp[n][n-1]) + cave[n][n]

  
  # print('Problem '+str(count)+ ":",  dpf(n-1, n-1, dp, cave, n))
  
  for d in dp:
    print(d)
  count += 1

왼쪽 위에서 오른쪽 아래로 진행하길래 당연히 DP라고 생각했다. 문제를 제대로 안 읽은 것이다. 그래서 오른쪽과 아래로만 진행되도록해서 처음에 풀었으나 두 번째 테스트케이스에서 19가 나왔다.
그래서 상하좌우 전부 탐색하도록 함수를 고쳤더니 무한 재귀가 일어났다.
dpf에서 값을 정해주지 않은 값끼리 서로 참조해서 생기는 문제였다.

시도 2 - 다익스트라

from heapq import heappush, heappop

dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]
count = 1
while True:
  n = int(input())
  
  if n == 0:
    break
  cave = list(list(map(int, input().split())) for _ in range(n))
  dist = [[n * n * 100] * n for _ in range(n)]
  
  dist[0][0] = cave[0][0]
  
  q = [(dist[0][0], 0, 0)]
  
  while q:
    cost, y, x = heappop(q)
    
    if dist[y][x] < cost:
      continue
    
    for d in range(4):
      ny = y + dy[d]
      nx = x + dx[d]
      
      if 0 <= ny < n and 0 <= nx < n and dist[ny][nx] > cost + cave[ny][nx]:
        dist[ny][nx] = cost + cave[ny][nx]
        heappush(q, (dist[ny][nx], ny, nx))
        
  print('Problem '+str(count)+ ":",  dist[-1][-1])
  count += 1

다익스트라로 해결했다. 보통 간선이 주어지면 인접 리스트를 만들어서 탐색했는데 이번에는 2차원 배열로 주어져서 간만에 dy, dx를 소환한 것 같다.

방향이 오른쪽, 아래로 한정되어 있다면 DP도 가능했겠는데 이번엔 상하좌우 전부 탐색대상이어서 실패한 것 같다. 문제를 제대로 읽고 조건을 잘 살펴봐야겠다.